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

杨利霞

（算法）通俗易懂的字符串匹配KMP算法及求next值算法
' f0 U2 l- f7 o" Z, j7 K% |# B
大多数据结构课本中，串涉及的内容即串的模式匹配，需要掌握的是朴素算法、KMP算法及next值的求法。在考研备考中，参考严奶奶的教材，我也是在关于求next值的算法中卡了一下午时间，感觉挺有意思的，把一些思考的结果整理出来，与大家一起探讨。

# l/ o/ b( z3 W2 c+ z4 x. ?
本文的逻辑顺序为
8 Y% E$ H8 M/ h* `0 Z; Z  e. ?1、最基本的朴素算法
2、优化的KMP算法
3、应算法需要定义的next值
4、手动写出较短串的next值的方法
% l' J* }4 W3 d! y5、最难理解的、足足有5行的代码的求next值的算法
" C: g/ U; }( l. t" G& g/ z所有铺垫为了最后的第5点，我觉得以这个逻辑下来，由果索因还是相对好理解的，下面写的很通俗，略显不专业…


一、问题描述
给定一个主串S及一个模式串P，判断模式串是否为主串的子串；若是，返回匹配的第一个元素的位置（序号从1开始），否则返回0；如S=“abcd”，P=“bcd”，则返回2；S=“abcd”，P=“acb”，返回0。


1 v) t# k6 m$ n' Q% g! p; m二、朴素算法
& }* y1 D9 C  E! U1 ~: ^最简单的方法及一次遍历S与P。以S=“abcabaaaabaaacac”,P="abaabcac"为例，一张动图模拟朴素算法：
+ L( q, @: |5 G+ p" H9 S# M0 Y6 J

  b# X) C: l! E! ?
3 y3 _) K$ J5 Z2 a$ `1 K. w4 y
, |# w3 B% o2 K这个算法简单，不多说，附上代码


#include<stdio.h>
' I6 C! d" D+ Q! ?' {' F2 d0 Dint Index_1(char s[],int sLen,char p[],int pLen){//s为主串，sLen为主串元素个数，p为模式串，pLen为模式串的个数
    if(sLen<pLen)return 0;
    int i = 1,j = 1;
    while(i<=sLen && j<=pLen){
6 c% c$ i5 D" X        if(s==p[j]){i++;j++;}
        else{
4 t7 s+ ^' n1 H4 Y# ^4 T& k            i = i-j+2;
            j = 1;
        }
5 t4 I' ?( S- y  `; ?- {    }
    if(j>pLen) return i-pLen;
    return 0;
/ E! U& f( z- \! ?" a$ M}
9 c% v- e6 p* _void main(){
5 D2 D. i4 d- u1 r. T    char s[]={' ','a','b','c','a','b','a','a','a','a','b','a','a','b','c','a','c'};//从序号1开始存
( M  ~6 K3 C( ?' Z2 \1 E+ m5 J3 s    char p[]={' ','a','b','a','a','b','c','a','c'};
    int sLen = sizeof(s)/sizeof(char)-1;
8 d. W0 J# m6 m. ~( ~    int pLen = sizeof(p)/sizeof(char)-1;
; Q6 p) x5 G' Z, j/ O% b, v    printf("%d",Index_1(s,sLen,p,pLen));
4 S, B- `. ~* u& v2 ?! F}
0 k" M; t: k( U" l1
+ W7 y! p1 O/ W3 F2
3
5 j4 h8 x" ~8 I$ X% q4
( Y$ Y$ V6 o/ Z5 |5
- T  i- v! l8 Z+ {9 m; A6
7
; r# _7 ~' u. z9 b$ i& E/ S8
- Q# D$ {; J: w. P2 Y  d" ^9
# Q7 g/ N3 A1 _+ s; P! ]10
11
: I. d' c1 o1 \12
' M# X* V2 V# z- l13
- b' z9 e) r$ W( Y8 Y14
15
: B7 _* \, `% w' ~; P8 H16
17
7 }# E8 G" ~3 W3 l+ d; \) [18
. |3 D/ b9 f1 Z  j" b4 b# @19
20
21
+ [, B9 |$ n' j* ]( k* V1 g三、改进的算法——KMP算法
" d% d8 L# v0 D* G9 P5 A朴素算法理解简单，但两个串都有依次遍历，时间复杂度为O(n*m)，效率不高。由此有了KMP算法。
) K! ^" ~2 v* O% ~; d一般的，在一次匹配中，我们是不知道主串的内容的，而模式串是我们自己定义的。
9 h7 t- W! {  w: ^朴素算法中，P的第j位失配，默认的把P串后移一位。
但在前一轮的比较中，我们已经知道了P的前(j-1)位与S中间对应的某(j-1)个元素已经匹配成功了。这就意味着，在一轮的尝试匹配中，我们get到了主串的部分内容，我们能否利用这些内容，让P多移几位(我认为这就是KMP算法最根本的东西)，减少遍历的趟数呢？答案是肯定的。再看下面改进后的动图：
5 K/ y$ ?: {9 m, L* D8 _

( }+ Y9 Q- C4 S8 z% u! Y6 p
- a/ l1 {* u5 r/ `
这个模拟过程即KMP算法，若没有看明白，继续往下看相应的解释，理解需要把P多移几位，然后回头再看一遍这个图就很明了了。

, O, N' i- o8 h8 r0 m
# U4 N" l, c  |% L, Q! t! J5 d8 N相比朴素算法：
& d: p8 l$ ]* C  x5 v& Y# b朴素算法： 每次失配，S串的索引i定位的本次尝试匹配的第一个字符的后一个。P串的索引j定位到1；T(n)=O(n*m)
9 m8 t6 h- Y3 g6 u* }9 }- dKMP算法： 每次失配，S串的索引i不动，P串的索引j定位到某个数。T(n)=O(n+m)，时间效率明显提高


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


+ o' K- {& g2 l6 Q2 ^, X1 d! }开——始——划——重——点！（图对逻辑关系比较好理解，但i和j的关系对后面求next的算法好理解！）

$ M& k6 z" \2 U4 U) V: U! g6 M, G
3 t8 @0 q  R" ]4 A比如，Pj处失配，绿色的是Pj，则我们可以确定P1…Pj-1是与Si…Si+j-2相对应的位置一一相等的

$ u3 X9 o: k9 s3 }5 p) [9 r% q

4 U& b- Y* ]* @7 W  g/ Z假设P1…Pj-1中，P1…Pk-1与Pj-k+1…Pj-1是一一相等的，为了下面说的清楚，我们把这种关系叫做“首尾重合”

$ y/ ~& Z3 [/ N$ m

6 e% t# R& x6 R% \1 C
  x9 a1 i$ n/ P0 ~那么可以推出，P1…Pk-1与Si…Si+j-2

, {: O/ D; J- ?
4 ?# E) t* a' A( ^. _/ Y3 O
. {+ R$ E# P- g& h( C  D7 f" G
* @) Y% v! s. b' k, r) F显然，接下来要做的就是把模式串右移了，移到哪里就不用多说了：
" P5 C' c! r, P# B! m- m9 m9 o9 }

) Q# j3 A+ n8 s8 J# r8 D8 T# J
& \3 c; |0 Q- t2 K4 X* {
1 d) e! `- r7 G. u: Y% H9 ^为了表示下一轮比较j定位的地方，我们将其定义为next[j]，next[j]就是第j个元素前j-1个元素首尾重合部分个数加一，当然，为了能遍历完整，首尾重合部分的元素个数应取到最多，即next[j]应取尽量大的值，原因挺好理解的，可以想个例子模拟一下，会完美跳过正确结果。在上图中就是绿色元素的next值为蓝色元素的序号。也即，对于字符串P，next[8]=4。如此，再看一下上面的动图是不是清楚了不少。
2 t0 D" I% U$ X% D
- N* L: q* e) e0 X$ b5 H
最后，如果我们知道了一个字符串的next值，那么KMP算法也就很好懂了。相比朴素算法，当发生失配时，i不变，j=next[j]就好啦！接下来就是怎么确定next值了。


四、手动写出一个串的next值
我们规定任何一个串，next[1]=0。(不用next[0]，与串的所有对应)，仍是一张动图搞定问题：

! K) v+ h  ^6 e8 s9 u/ l4 ]- s
这个扫一眼就能依次写出，会了这个方法，应付个期末考试没问题了。
8 w. y" ~# d$ E: o4 w- q) ?
* ~6 [7 q( a' w- R) K, x
" e9 e2 u! E8 l通过把next值“看”出来，我们再来分析next值，这就很容易得到超级有名的公式了，这个式子对后面的算法理解很重要！所以先要看懂这个式子，如果上面的内容通下来了，这个应该很容易看懂了：

: Y$ O3 i. O. w0 s
9 z% V+ [' E5 l0 r1 g

五、求next的算法
' X8 T  L1 W. S. g" N6 ^  ?终于到了最后了~短的串的next值我们可以“看”出来，但长的串就需要借助程序了，具体算法刚接触的时候确实不容易理解，但给我的体验，把上面的内容写完，现在感觉简简单单了…先附上程序再做解释，(终于到了传说中的整整5行代码让我整理了一下午)。
* F# ]4 e: u8 z5 q0 M

+ e( f9 s+ O3 C8 z8 T# F1 _8 \int GetNext(char ch[],int cLen,int next[]){//cLen为串ch的长度
2 d" `  e, e5 }) A    next[1] = 0;
1 d3 z% s' L' ]4 ^  O9 p  l    int i = 1,j = 0;
    while(i<=cLen){
  ^/ D6 U6 ^  N        if(j==0||ch==ch[j]) next[++i] = ++j;
        else j = next[j];
    }
# w: ~7 r% \2 {- `' v2 J}
* `4 Y/ O  Q, b( j# ?, ]% N
还是先由一般再推优化：
6 T  z9 W% a/ S- g. h! u直接求next[j+1]（至于为什么是j+1，是为了和下面的对应）
/ |3 h6 Y% }$ ?; a根据之前的分析，next[j+1]的值为pj+1的前j个元素的收尾重合的最大个数加一。即需要满足两个条件，把它的值一步步“检验”出来。一是“个数最多”的，因此要从可能的最大值开始验；二是“首尾重合”，因此要一一对应验是否相等。
不难理解，next[j+1]的最大值为j，所有我们从next[j+1]=j开始“验证”。有以下优先判断顺序：
if(P1…Pj-1 == P2…Pj) => next[j+1]=j
else if(P1…Pj-2 == P3…Pj) =>next[j+1]=j-1
5 X& w1 z2 H  @3 celse if(P1…Pj-3 == P4…Pj) =>next[j+1]=j-2
$ J' ~* N: J  b' C( R% n…
…
8 K( E* C( T4 V4 F+ f; O/ Q…
else if(P1P2 == Pj-1Pj) => next[j+1]=3
else if(P1 == Pj-1) => next[j+1]=2
4 z+ b6 b4 z6 I; S5 i' {else if(P1 != Pj-1) => next[j+1]=1
9 N1 [  z8 Q  ~8 ]! |  r. y" ]每次前去尾1个，后掐头1个，直至得到next[j+1]
. e" B9 G3 U! y" N+ m6 [# e" W
! \# ]0 w7 ^& E% y8 P4 k
3 G8 ]; R7 R4 z; k( F; W+ K再进一步想，next值是一个“工具”，我们单独的求next[j+1]是完全没有意义的，就是说要求next就要把所有j的next求出来。所有一般的，我们都是已知前j个元素的next值，求next[j+1]，以此递推下去，求完整的next数组。
* Y1 h+ q, t& `* D但是，上面的思考过程还是最根本的。所以问题变为两个：知道前j个元素的next的情况下，
①next[j+1]的可能的最大值是多少（即从哪开始验证）
②某一步验证失败后，需要“前去尾几个，后掐头几个？”（即本次验证失败后，再验证哪个值）
看一下的分析：


1、next[j+1]的最大值为next[j]+1。
因为：
假设next[j]=k1，则可以说明P1…Pk1-1=Pj-k1+1…Pj-1，且这是前j个元素最大的首尾重合序列。
3 j$ D! Y$ K5 j* ~) O如果Pk1=Pj，那么P1…Pk1-1PK=Pj-k1+1…Pj-1Pj，那么k+1这也是前j+1个元素的最大首尾重合序列，也即next[j+1]的值为k1+1
6 ^4 S, E# j# p2 _" |2、如果Pk1≠Pj，那么next[j+1]可能的次大值为next[next[j]]+1，以此类推即可高效求出next[j+1]
: q& i5 b2 Y9 b9 K( t* ^1 x* A这里不好解释，直接看下面的流程分析及图解


+ E% B9 k; Y- n+ `5 y开——始——划——重——点！
* O& j2 g9 P5 p& a/ `从头走一遍流程
: \' I" q" F7 O. {/ l①求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，否则
5 x' m+ @  V- i4 L④已知next[k1]=k2，则有P1…Pk2-1 = Pk1-k2+1…Pk1-1
⑤第二第三步联合得到:
P1…Pk2-1 = Pk1-k2+1…Pk1-1 = Pj-k1+1…Pk2-k1+j-1 = Pj-k2+1…Pj-1 即四段重合
/ l. B, z( }) T8 u* H) v& b⑥这时候，再判断如果Pk2=Pj，则P1…Pk2-1P~k2 = Pj-k2+1…Pj-1Pj，则next[j+1]=k2+1；否则再取next[k2]=k3…以此类推


上面几步，耐心看下来，结合那个式子很容易看懂。最后，再加一个图的模拟帮助理解：
/ Q7 N+ n& {0 L( S1、要求next[k+1] 其中k+1=17
+ h9 ~( X+ M( M7 Y/ K
$ j1 {1 T" @+ o" u' p
2、已知next[16]=8，则元素有以下关系：

$ L& H2 u- p& T4 m/ }' k, }7 t
3、如果P8=P16，则明显next[17]=8+1=9
2 K; t$ E# ^$ G# P/ c3 z4 p) y4、如果不相等，又若next[8]=4，则有以下关系
5 l+ ?9 {6 E6 ?. z
6 h9 F. ^; l7 `4 J& b8 a" L
又加上2的条件知

+ Q- A; {# e4 M6 z5 m9 v
! Y6 ^" z% b; ^, ~主要是为了证明：


8 h9 l- ~# M" P0 s' t# u5、现在在判断，如果P16=P4则next[17]=4+1=5，否则，在继续递推
6、若next[4]=2，则有以下关系
& ]6 U2 L) f5 P7 J
( m2 l3 |( `1 p) j6 q9 o3 u" l
% p7 ~/ J) L2 u1 F3 V7 O7、若P16=P2，则next[17]=2+1=3;否则继续取next[2]=1、next[1]=0；遇到0时还没出结果，则递推结束，此时next[17]=1。最后，再返回看那5行算法，应该很容易明白了！
————————————————
版权声明：本文为CSDN博主「Sirm23333」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
# D+ Q% `; G6 K原文链接：https://blog.csdn.net/qq_37969433/article/details/82947411
. ]6 i5 Z8 ?8 K) L* c8 M: l
7 A8 K* A# [* [2 P- Y. z: l" C
, d8 ^, o) m, l0 ^! a
( }! N8 g' Z5 f9 _& j" U8 g3 s9 \