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

杨利霞

（算法）通俗易懂的字符串匹配KMP算法及求next值算法
/ T! s* [1 m5 f# K$ u
9 g" E& R! R' O4 ]; d% R% z大多数据结构课本中，串涉及的内容即串的模式匹配，需要掌握的是朴素算法、KMP算法及next值的求法。在考研备考中，参考严奶奶的教材，我也是在关于求next值的算法中卡了一下午时间，感觉挺有意思的，把一些思考的结果整理出来，与大家一起探讨。

+ p: j6 G. ^+ J8 L* s% K& D, t
本文的逻辑顺序为
1、最基本的朴素算法
2、优化的KMP算法
" a+ y' I) l( K9 _$ p) t+ Y1 d/ O& @3、应算法需要定义的next值
4、手动写出较短串的next值的方法
' l1 _& u. U! k; A$ M$ M- W7 v5、最难理解的、足足有5行的代码的求next值的算法
: `$ V+ R5 f9 Q7 Y8 }! g5 l所有铺垫为了最后的第5点，我觉得以这个逻辑下来，由果索因还是相对好理解的，下面写的很通俗，略显不专业…
: _8 w7 P9 Q( U% C: S) M2 H

" u# }; O5 i; A. L一、问题描述
% o- M, P7 b3 j. H2 m) K给定一个主串S及一个模式串P，判断模式串是否为主串的子串；若是，返回匹配的第一个元素的位置（序号从1开始），否则返回0；如S=“abcd”，P=“bcd”，则返回2；S=“abcd”，P=“acb”，返回0。


二、朴素算法
% ~% S( Y  \3 r, u9 _+ v8 t最简单的方法及一次遍历S与P。以S=“abcabaaaabaaacac”,P="abaabcac"为例，一张动图模拟朴素算法：


) d. d1 j5 ?' e/ `

" E6 w+ I$ m; H2 y8 {/ f这个算法简单，不多说，附上代码
& V2 T# k5 \) i+ y+ C) v' V

* L$ i% I$ w4 i/ N#include<stdio.h>
' |" f, K# M- }* V" M' ]int Index_1(char s[],int sLen,char p[],int pLen){//s为主串，sLen为主串元素个数，p为模式串，pLen为模式串的个数
* X/ Z4 N, f. B4 N- z  q  e    if(sLen<pLen)return 0;
0 Z: k( p0 L1 l9 p# a    int i = 1,j = 1;
! C( Y: W# ~, E- k    while(i<=sLen && j<=pLen){
3 r% A/ u" W- F/ J3 \/ s+ b        if(s==p[j]){i++;j++;}
- K# }7 n( Z( ~, Y$ @        else{
& k7 J( v( Q1 F- h# x3 ?            i = i-j+2;
            j = 1;
        }
    }
" D/ R* O! [3 D& N    if(j>pLen) return i-pLen;
    return 0;
}
void main(){
8 }5 Q$ ]1 c/ L/ V' P) Y    char s[]={' ','a','b','c','a','b','a','a','a','a','b','a','a','b','c','a','c'};//从序号1开始存
    char p[]={' ','a','b','a','a','b','c','a','c'};
* h7 m  U+ f& G2 {& [- W; q    int sLen = sizeof(s)/sizeof(char)-1;
. X1 H% H3 r2 e: w( q    int pLen = sizeof(p)/sizeof(char)-1;
    printf("%d",Index_1(s,sLen,p,pLen));
/ ^; T1 n  Y/ K# S}
1
4 u0 d+ b8 J) q) _( i  l6 P2 w) X" y7 f2
, E9 Z, P7 J0 X+ U3
4
1 X+ R2 z. m7 R4 G$ j: o3 F6 v4 c5
6 Z. \1 _# d( n* M4 @* V6
7 ]0 P+ u3 j- _" D% T7
8
# C4 V, u1 o/ X- `. z* T9
10
11
9 b2 l  l" T) j' y7 `' D12
% B0 M) G  o2 C. k13
' a, f( `5 a; `( _% t+ h14
7 d) }6 s  r0 f% u15
5 x) L, F% c: S# F16
( _& M5 O" p4 C' L, Y17
18
19
7 z' g" ^+ G8 l# T  O( J20
21
3 P" b% r" @: M1 I6 g$ t三、改进的算法——KMP算法
' {. `; y/ `% ~' o' y; u$ M" i朴素算法理解简单，但两个串都有依次遍历，时间复杂度为O(n*m)，效率不高。由此有了KMP算法。
  @/ ?, I" y4 u+ x2 y( N1 y, G一般的，在一次匹配中，我们是不知道主串的内容的，而模式串是我们自己定义的。
朴素算法中，P的第j位失配，默认的把P串后移一位。
但在前一轮的比较中，我们已经知道了P的前(j-1)位与S中间对应的某(j-1)个元素已经匹配成功了。这就意味着，在一轮的尝试匹配中，我们get到了主串的部分内容，我们能否利用这些内容，让P多移几位(我认为这就是KMP算法最根本的东西)，减少遍历的趟数呢？答案是肯定的。再看下面改进后的动图：
, j9 G' M9 C1 h6 @
' Q! e4 z- a3 o. _; j6 @* a* f5 t


这个模拟过程即KMP算法，若没有看明白，继续往下看相应的解释，理解需要把P多移几位，然后回头再看一遍这个图就很明了了。


: ]& i( b( E- N0 w  l- ^相比朴素算法：
朴素算法： 每次失配，S串的索引i定位的本次尝试匹配的第一个字符的后一个。P串的索引j定位到1；T(n)=O(n*m)
KMP算法： 每次失配，S串的索引i不动，P串的索引j定位到某个数。T(n)=O(n+m)，时间效率明显提高
. ]( X; B+ Q; O

! B" a. D: p0 e0 _' j而这“定位到某个数”，这个数就是接下来引入的next值。（实际上也就是P往后移多少位，换一种说法罢了：从上图中也可以看出，失配时固定i不变，令S与P[某个数]对齐，实际上是P右移几位的另一种表达，只有为什么这么表达，当然是因为程序好写。）
6 p2 K& ?4 D3 T

$ c% Z# E* Z' F* p1 l- y( x开——始——划——重——点！（图对逻辑关系比较好理解，但i和j的关系对后面求next的算法好理解！）
  A+ g5 ]" u/ d" |; A+ L9 C
& f6 f7 O5 W+ d+ _9 _+ v) p
比如，Pj处失配，绿色的是Pj，则我们可以确定P1…Pj-1是与Si…Si+j-2相对应的位置一一相等的
: E; }& d1 U# h$ b

& v2 p1 V8 ]4 r4 e
+ c* V7 C0 y4 ]" f$ J/ l假设P1…Pj-1中，P1…Pk-1与Pj-k+1…Pj-1是一一相等的，为了下面说的清楚，我们把这种关系叫做“首尾重合”
6 ~9 L  B7 ^9 s6 {0 p9 P
) P' T8 Z3 _7 F1 x3 m

8 [( k4 n* Q: r& W$ W% w5 m  N
那么可以推出，P1…Pk-1与Si…Si+j-2

- F7 m9 H6 G# z9 j' R  W4 d


2 Z5 j* ~( Y+ p6 S1 V2 k$ ~+ k1 p显然，接下来要做的就是把模式串右移了，移到哪里就不用多说了：
# X0 P- k, ~' z! @  q4 @8 ?: B# y


1 Q; J4 Z" f5 U* {% l4 @$ a
) P1 o/ ^% W! y+ K4 Y6 D7 p: v为了表示下一轮比较j定位的地方，我们将其定义为next[j]，next[j]就是第j个元素前j-1个元素首尾重合部分个数加一，当然，为了能遍历完整，首尾重合部分的元素个数应取到最多，即next[j]应取尽量大的值，原因挺好理解的，可以想个例子模拟一下，会完美跳过正确结果。在上图中就是绿色元素的next值为蓝色元素的序号。也即，对于字符串P，next[8]=4。如此，再看一下上面的动图是不是清楚了不少。
2 P8 w+ C5 {" X/ {9 B( T# B

/ q  P8 _1 _) A+ @; Z8 h( P最后，如果我们知道了一个字符串的next值，那么KMP算法也就很好懂了。相比朴素算法，当发生失配时，i不变，j=next[j]就好啦！接下来就是怎么确定next值了。
) E: c1 T1 K# q3 }" `
& ^. s  y1 m7 {% z- A5 u# n
四、手动写出一个串的next值
, v- _) E2 O1 E% @我们规定任何一个串，next[1]=0。(不用next[0]，与串的所有对应)，仍是一张动图搞定问题：
* R9 ~2 t$ b) @$ W; V

这个扫一眼就能依次写出，会了这个方法，应付个期末考试没问题了。

) f4 b( V5 S  C* b1 s
5 {3 \0 i% m9 I# j, L通过把next值“看”出来，我们再来分析next值，这就很容易得到超级有名的公式了，这个式子对后面的算法理解很重要！所以先要看懂这个式子，如果上面的内容通下来了，这个应该很容易看懂了：
4 m/ y' w  h+ _& N3 w2 I



  g( V: ~5 w6 S* i五、求next的算法
终于到了最后了~短的串的next值我们可以“看”出来，但长的串就需要借助程序了，具体算法刚接触的时候确实不容易理解，但给我的体验，把上面的内容写完，现在感觉简简单单了…先附上程序再做解释，(终于到了传说中的整整5行代码让我整理了一下午)。
- h3 v, z! @: A$ _2 V8 W
/ Z, F$ X7 t6 U3 l$ q2 o
int GetNext(char ch[],int cLen,int next[]){//cLen为串ch的长度
    next[1] = 0;
    int i = 1,j = 0;
    while(i<=cLen){
        if(j==0||ch==ch[j]) next[++i] = ++j;
        else j = next[j];
, a; j) r$ d& Q& l( T/ k$ O    }
}
4 k: }6 T# G( p4 w4 \
还是先由一般再推优化：
- _  k5 q. W6 J+ q% r3 K直接求next[j+1]（至于为什么是j+1，是为了和下面的对应）
5 O6 Q2 S9 P" Z8 k/ c/ j  X. a( _) q根据之前的分析，next[j+1]的值为pj+1的前j个元素的收尾重合的最大个数加一。即需要满足两个条件，把它的值一步步“检验”出来。一是“个数最多”的，因此要从可能的最大值开始验；二是“首尾重合”，因此要一一对应验是否相等。
: l0 A- L# _) E$ P  h: S不难理解，next[j+1]的最大值为j，所有我们从next[j+1]=j开始“验证”。有以下优先判断顺序：
if(P1…Pj-1 == P2…Pj) => next[j+1]=j
  E! a, g$ q1 Y9 l6 M& Q  X+ I3 telse if(P1…Pj-2 == P3…Pj) =>next[j+1]=j-1
4 t# ]$ o3 e5 R, Y6 |% G! Uelse if(P1…Pj-3 == P4…Pj) =>next[j+1]=j-2
" X" y4 S+ g% j) _) S7 ]; M…
6 [% _: {' j' G( \5 ?5 N5 ~…
…
else if(P1P2 == Pj-1Pj) => next[j+1]=3
/ \% S  W* V  [8 n% ]. ?0 K2 z9 [else if(P1 == Pj-1) => next[j+1]=2
% g+ d) z9 j% ~. J& ]( melse if(P1 != Pj-1) => next[j+1]=1
每次前去尾1个，后掐头1个，直至得到next[j+1]
% L( r) c# k: G: ]; g7 W; v

. Q8 x4 p6 z. w" b! B- m! D+ |; C再进一步想，next值是一个“工具”，我们单独的求next[j+1]是完全没有意义的，就是说要求next就要把所有j的next求出来。所有一般的，我们都是已知前j个元素的next值，求next[j+1]，以此递推下去，求完整的next数组。
' ?9 N7 G9 S/ J1 b3 X$ s: O- f但是，上面的思考过程还是最根本的。所以问题变为两个：知道前j个元素的next的情况下，
①next[j+1]的可能的最大值是多少（即从哪开始验证）
②某一步验证失败后，需要“前去尾几个，后掐头几个？”（即本次验证失败后，再验证哪个值）
看一下的分析：
7 }2 I0 S4 w% R6 n7 T* E6 @
% h; Y0 |' x5 O4 C1 t+ \
1、next[j+1]的最大值为next[j]+1。
7 p: n9 }3 ?9 c. T1 e, {: b0 a" z因为：
/ E6 f; w# y. g假设next[j]=k1，则可以说明P1…Pk1-1=Pj-k1+1…Pj-1，且这是前j个元素最大的首尾重合序列。
如果Pk1=Pj，那么P1…Pk1-1PK=Pj-k1+1…Pj-1Pj，那么k+1这也是前j+1个元素的最大首尾重合序列，也即next[j+1]的值为k1+1
- t" f7 v  S, [  ]8 Y1 p2、如果Pk1≠Pj，那么next[j+1]可能的次大值为next[next[j]]+1，以此类推即可高效求出next[j+1]
9 O9 b4 ?: Z3 M7 k2 T3 I5 T& [; P6 t这里不好解释，直接看下面的流程分析及图解

& a3 l! S3 r6 G8 ?# _1 L! T( g/ V* H, D
开——始——划——重——点！
从头走一遍流程
①求next[j+1]，设值为m
②已知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，否则
/ Q9 k5 [( ]  z! }- B④已知next[k1]=k2，则有P1…Pk2-1 = Pk1-k2+1…Pk1-1
⑤第二第三步联合得到:
; I4 C# h* n8 n2 S/ pP1…Pk2-1 = Pk1-k2+1…Pk1-1 = Pj-k1+1…Pk2-k1+j-1 = Pj-k2+1…Pj-1 即四段重合
: O# y9 b1 f1 P6 ^# d* C6 P⑥这时候，再判断如果Pk2=Pj，则P1…Pk2-1P~k2 = Pj-k2+1…Pj-1Pj，则next[j+1]=k2+1；否则再取next[k2]=k3…以此类推

: p& B" \) ^! J' \& f, E
+ Y' _/ D8 t6 s' K9 a5 G上面几步，耐心看下来，结合那个式子很容易看懂。最后，再加一个图的模拟帮助理解：
1、要求next[k+1] 其中k+1=17
7 u3 u; D4 s% Y6 [: k
+ G9 w5 J" Y) \. e
2、已知next[16]=8，则元素有以下关系：

; j$ Q* O* x7 Q( r/ X4 q# o
3、如果P8=P16，则明显next[17]=8+1=9
4、如果不相等，又若next[8]=4，则有以下关系


又加上2的条件知
  u9 @) {8 w2 I) U+ u
1 m( W! _" I2 F
主要是为了证明：

; u" N; I6 r2 n/ b
5 l. f9 }  T; z$ S9 `- y5、现在在判断，如果P16=P4则next[17]=4+1=5，否则，在继续递推
6、若next[4]=2，则有以下关系


7、若P16=P2，则next[17]=2+1=3;否则继续取next[2]=1、next[1]=0；遇到0时还没出结果，则递推结束，此时next[17]=1。最后，再返回看那5行算法，应该很容易明白了！
————————————————
) q( w0 b! c5 a* L版权声明：本文为CSDN博主「Sirm23333」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_37969433/article/details/82947411



( Q' q; m( V2 U" `5 X$ k$ p