（算法）通俗易懂的字符串匹配KMP算法及求next值算法

杨利霞

（算法）通俗易懂的字符串匹配KMP算法及求next值算法
2 O( \" C: w$ q! ?: V2 ?/ D/ R
大多数据结构课本中，串涉及的内容即串的模式匹配，需要掌握的是朴素算法、KMP算法及next值的求法。在考研备考中，参考严奶奶的教材，我也是在关于求next值的算法中卡了一下午时间，感觉挺有意思的，把一些思考的结果整理出来，与大家一起探讨。


6 m) }; {; y% ^2 z. M5 \9 w' I% ^本文的逻辑顺序为
1、最基本的朴素算法
4 D# U, n6 [3 v/ y) i- y5 L2、优化的KMP算法
. P+ `( [' p8 a0 P3、应算法需要定义的next值
6 }  @" X& W/ _, K4、手动写出较短串的next值的方法
$ q. K5 o$ r, l: i5、最难理解的、足足有5行的代码的求next值的算法
所有铺垫为了最后的第5点，我觉得以这个逻辑下来，由果索因还是相对好理解的，下面写的很通俗，略显不专业…


' U0 m  r9 e, x1 ~' l一、问题描述
: [/ s+ H: x& a- p6 e4 S% W给定一个主串S及一个模式串P，判断模式串是否为主串的子串；若是，返回匹配的第一个元素的位置（序号从1开始），否则返回0；如S=“abcd”，P=“bcd”，则返回2；S=“abcd”，P=“acb”，返回0。
& X7 @6 y6 \( ]. I3 i6 w
0 \2 r4 x, o4 H
二、朴素算法
; Z# m; J4 g  O, b最简单的方法及一次遍历S与P。以S=“abcabaaaabaaacac”,P="abaabcac"为例，一张动图模拟朴素算法：

3 Y+ `( m  z' s5 w) b


这个算法简单，不多说，附上代码


#include<stdio.h>
int Index_1(char s[],int sLen,char p[],int pLen){//s为主串，sLen为主串元素个数，p为模式串，pLen为模式串的个数
6 T/ |# C: v( X0 v# K; l: Q$ ~    if(sLen<pLen)return 0;
6 N& i& L6 S! H2 @7 b# I    int i = 1,j = 1;
    while(i<=sLen && j<=pLen){
        if(s==p[j]){i++;j++;}
        else{
            i = i-j+2;
            j = 1;
        }
; }" ~# O0 O8 |8 g. O3 c    }
; o. e$ }! k& p    if(j>pLen) return i-pLen;
6 w6 k8 t* t3 S4 S/ Z. n9 P0 h    return 0;
}
! p8 M1 j( H; ]$ V' j3 Y  U/ s- Zvoid main(){
: g0 N! _& |8 Z7 i) _5 A    char s[]={' ','a','b','c','a','b','a','a','a','a','b','a','a','b','c','a','c'};//从序号1开始存
' C, n. `+ o: R9 x( m    char p[]={' ','a','b','a','a','b','c','a','c'};
, X  l- j5 c' g: E% P9 o  w9 b5 M    int sLen = sizeof(s)/sizeof(char)-1;
* x, y  M0 \* {2 a& V    int pLen = sizeof(p)/sizeof(char)-1;
5 G' I2 Y' d$ ]8 X- f    printf("%d",Index_1(s,sLen,p,pLen));
}
5 e4 o' }% b6 T& d0 w. Y; d1
2
9 s7 Y. j- _+ G1 W+ _) W9 G0 q3
4
2 d7 J1 H) i9 ^! K; i5
* b$ k, N# X  Q1 j# C  q* l6 e( v6
7 p7 y* R& v' g6 y7
8
0 g6 C  q' i. W9
% g" l3 N& l9 W10
11
12
9 ]& U, g# e: f  ?) [13
14
& ?- E: ~5 v% X( q$ o) `15
16
8 }7 ]' X  Y( a; V4 j3 _) z17
18
19
20
21
9 Y- @5 C/ F' }  k1 c0 V$ D+ t三、改进的算法——KMP算法
朴素算法理解简单，但两个串都有依次遍历，时间复杂度为O(n*m)，效率不高。由此有了KMP算法。
一般的，在一次匹配中，我们是不知道主串的内容的，而模式串是我们自己定义的。
; Q$ A1 o, v1 c+ f9 v朴素算法中，P的第j位失配，默认的把P串后移一位。
, L& m: Q; c& X1 }% B& z但在前一轮的比较中，我们已经知道了P的前(j-1)位与S中间对应的某(j-1)个元素已经匹配成功了。这就意味着，在一轮的尝试匹配中，我们get到了主串的部分内容，我们能否利用这些内容，让P多移几位(我认为这就是KMP算法最根本的东西)，减少遍历的趟数呢？答案是肯定的。再看下面改进后的动图：

% H8 j+ ?' ]8 X- M0 n$ U


; m' t, R0 x! _( C: K9 v" Q# A这个模拟过程即KMP算法，若没有看明白，继续往下看相应的解释，理解需要把P多移几位，然后回头再看一遍这个图就很明了了。
4 B* B( ^$ w" K1 L
4 A% L& ]* V, @8 e) m# S
相比朴素算法：
朴素算法： 每次失配，S串的索引i定位的本次尝试匹配的第一个字符的后一个。P串的索引j定位到1；T(n)=O(n*m)
KMP算法： 每次失配，S串的索引i不动，P串的索引j定位到某个数。T(n)=O(n+m)，时间效率明显提高
" ]* T5 J7 s. C% ~) M1 A# w. b
7 I, O0 Y; ]6 r+ F8 R! m1 V
3 X, K8 b) A0 e3 M- e; X3 }而这“定位到某个数”，这个数就是接下来引入的next值。（实际上也就是P往后移多少位，换一种说法罢了：从上图中也可以看出，失配时固定i不变，令S与P[某个数]对齐，实际上是P右移几位的另一种表达，只有为什么这么表达，当然是因为程序好写。）


+ r3 N6 W$ p9 _; K+ t开——始——划——重——点！（图对逻辑关系比较好理解，但i和j的关系对后面求next的算法好理解！）
0 Q2 |% }" @2 o' ]
8 V  y9 t' p; C# T" {- m/ Q
2 m5 U6 M9 L0 L% \0 I3 [比如，Pj处失配，绿色的是Pj，则我们可以确定P1…Pj-1是与Si…Si+j-2相对应的位置一一相等的
& }$ M3 e$ ~2 r2 X- J1 p
, @, T" i) q/ u2 S$ {

假设P1…Pj-1中，P1…Pk-1与Pj-k+1…Pj-1是一一相等的，为了下面说的清楚，我们把这种关系叫做“首尾重合”
% `$ b6 H8 L4 `- S# N9 B6 g
  k* T7 X& `0 i% e9 ~; Y
) k6 m' l8 c, k$ Q! @& f) S
. w3 {) }5 i. L+ i) z; h
. v: D/ r0 j& W% h4 i4 k2 O那么可以推出，P1…Pk-1与Si…Si+j-2

) O9 M$ o5 M# P% w


# p* ]: Q# N' i9 p显然，接下来要做的就是把模式串右移了，移到哪里就不用多说了：


  {, Y3 k5 s: i& N

为了表示下一轮比较j定位的地方，我们将其定义为next[j]，next[j]就是第j个元素前j-1个元素首尾重合部分个数加一，当然，为了能遍历完整，首尾重合部分的元素个数应取到最多，即next[j]应取尽量大的值，原因挺好理解的，可以想个例子模拟一下，会完美跳过正确结果。在上图中就是绿色元素的next值为蓝色元素的序号。也即，对于字符串P，next[8]=4。如此，再看一下上面的动图是不是清楚了不少。
% l% [$ y( _- J. ?, I6 S9 x2 h6 G# ^

* U1 m# @+ U; B! F) O" j; l最后，如果我们知道了一个字符串的next值，那么KMP算法也就很好懂了。相比朴素算法，当发生失配时，i不变，j=next[j]就好啦！接下来就是怎么确定next值了。


, U" }  {( l& Z" P9 [) G, z- f, d四、手动写出一个串的next值
我们规定任何一个串，next[1]=0。(不用next[0]，与串的所有对应)，仍是一张动图搞定问题：


这个扫一眼就能依次写出，会了这个方法，应付个期末考试没问题了。
8 ?6 E$ @, }3 t

. y0 x) R! H; k' C通过把next值“看”出来，我们再来分析next值，这就很容易得到超级有名的公式了，这个式子对后面的算法理解很重要！所以先要看懂这个式子，如果上面的内容通下来了，这个应该很容易看懂了：




五、求next的算法
$ f0 K, l5 G- {3 [; n终于到了最后了~短的串的next值我们可以“看”出来，但长的串就需要借助程序了，具体算法刚接触的时候确实不容易理解，但给我的体验，把上面的内容写完，现在感觉简简单单了…先附上程序再做解释，(终于到了传说中的整整5行代码让我整理了一下午)。


( ], v9 Z7 j' g; vint GetNext(char ch[],int cLen,int next[]){//cLen为串ch的长度
    next[1] = 0;
    int i = 1,j = 0;
) ]- r- Z8 ^5 v( I    while(i<=cLen){
        if(j==0||ch==ch[j]) next[++i] = ++j;
, O- B7 w7 `0 v3 H        else j = next[j];
  N3 U0 `/ a$ {+ m; ^. P8 q    }
9 `) ?( ], b# E7 M7 W" I+ U2 H}
+ U! E* _0 N0 ?5 @" j0 p
& f" b; D, ]( |) [8 A/ P6 V7 k3 u- w6 |# G还是先由一般再推优化：
直接求next[j+1]（至于为什么是j+1，是为了和下面的对应）
根据之前的分析，next[j+1]的值为pj+1的前j个元素的收尾重合的最大个数加一。即需要满足两个条件，把它的值一步步“检验”出来。一是“个数最多”的，因此要从可能的最大值开始验；二是“首尾重合”，因此要一一对应验是否相等。
不难理解，next[j+1]的最大值为j，所有我们从next[j+1]=j开始“验证”。有以下优先判断顺序：
if(P1…Pj-1 == P2…Pj) => next[j+1]=j
$ K8 t0 U7 U0 N' j; a9 aelse if(P1…Pj-2 == P3…Pj) =>next[j+1]=j-1
else if(P1…Pj-3 == P4…Pj) =>next[j+1]=j-2
…
5 n, \; S7 }# l- I…
1 E0 p0 D* D8 B$ r! S; C8 f9 A6 […
else if(P1P2 == Pj-1Pj) => next[j+1]=3
else if(P1 == Pj-1) => next[j+1]=2
- E% @5 H/ m; U% Belse if(P1 != Pj-1) => next[j+1]=1
/ J0 g: Y; I) K7 A1 q每次前去尾1个，后掐头1个，直至得到next[j+1]
7 N/ i& j2 H. M
" y3 h" o# @. d/ z& i
/ I9 s' d$ y" p9 e4 s再进一步想，next值是一个“工具”，我们单独的求next[j+1]是完全没有意义的，就是说要求next就要把所有j的next求出来。所有一般的，我们都是已知前j个元素的next值，求next[j+1]，以此递推下去，求完整的next数组。
; |0 Z1 S( ?& E8 M) P但是，上面的思考过程还是最根本的。所以问题变为两个：知道前j个元素的next的情况下，
7 g- h: h) p5 @0 C①next[j+1]的可能的最大值是多少（即从哪开始验证）
$ k9 j& g+ n# O. c: s②某一步验证失败后，需要“前去尾几个，后掐头几个？”（即本次验证失败后，再验证哪个值）
看一下的分析：
6 T/ j+ r! `8 K: b

1、next[j+1]的最大值为next[j]+1。
因为：
) `5 v7 }9 `; V0 h假设next[j]=k1，则可以说明P1…Pk1-1=Pj-k1+1…Pj-1，且这是前j个元素最大的首尾重合序列。
- ?$ E. d8 g" h) E+ d1 I如果Pk1=Pj，那么P1…Pk1-1PK=Pj-k1+1…Pj-1Pj，那么k+1这也是前j+1个元素的最大首尾重合序列，也即next[j+1]的值为k1+1
! r6 L( D: l4 ^; _* O% D" ?7 y: \: T2、如果Pk1≠Pj，那么next[j+1]可能的次大值为next[next[j]]+1，以此类推即可高效求出next[j+1]
这里不好解释，直接看下面的流程分析及图解

' G0 i8 V4 j& N' U
开——始——划——重——点！
从头走一遍流程
①求next[j+1]，设值为m
: r! X9 @7 ^. s8 ?8 T②已知next[j]=k1，则有P1…Pk1-1 = Pj-k1+1…Pj-1
③如果Pk1=Pj，则P1…Pk1-1PK = Pj-k1+1…Pj-1Pj，则next[j+1]=k1+1，否则
' t1 A4 T, [  O" ?④已知next[k1]=k2，则有P1…Pk2-1 = Pk1-k2+1…Pk1-1
⑤第二第三步联合得到:
8 y2 p+ ?6 p- l5 L5 Q4 d2 A6 }! ^P1…Pk2-1 = Pk1-k2+1…Pk1-1 = Pj-k1+1…Pk2-k1+j-1 = Pj-k2+1…Pj-1 即四段重合
" q9 }+ n0 e% L; Q, c& g, N⑥这时候，再判断如果Pk2=Pj，则P1…Pk2-1P~k2 = Pj-k2+1…Pj-1Pj，则next[j+1]=k2+1；否则再取next[k2]=k3…以此类推


上面几步，耐心看下来，结合那个式子很容易看懂。最后，再加一个图的模拟帮助理解：
/ j5 B7 F; k5 G  z+ q1、要求next[k+1] 其中k+1=17
1 x. N. r9 f' q( c$ o
* s& ^% ~$ x% T( l0 I! S! S$ \
2、已知next[16]=8，则元素有以下关系：
- c: d' q/ f& m
" E3 y/ Q2 i" f! C
& j: r8 z5 d2 o' g2 K' u% D5 V$ s; Z3、如果P8=P16，则明显next[17]=8+1=9
1 H0 n4 Q& U6 `& C9 c: \8 ^4、如果不相等，又若next[8]=4，则有以下关系
# B* R1 i4 F2 m
5 R# F/ o  N( Q5 e
& |  E* M# d& A; O$ p7 q又加上2的条件知

, d6 _6 g* r8 b7 x; M
主要是为了证明：

' T, X1 B/ y8 |9 t
5、现在在判断，如果P16=P4则next[17]=4+1=5，否则，在继续递推
6、若next[4]=2，则有以下关系
+ A" n9 t+ ]# t- r9 v% |. [

7、若P16=P2，则next[17]=2+1=3;否则继续取next[2]=1、next[1]=0；遇到0时还没出结果，则递推结束，此时next[17]=1。最后，再返回看那5行算法，应该很容易明白了！
9 o! M% g, Q, j2 T8 B————————————————
版权声明：本文为CSDN博主「Sirm23333」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
# A$ ~3 F3 n; k' Z原文链接：https://blog.csdn.net/qq_37969433/article/details/82947411


6 m: r# T* E4 G% r1 y