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

杨利霞

（算法）通俗易懂的字符串匹配KMP算法及求next值算法
; v/ ~+ p" l2 Z
大多数据结构课本中，串涉及的内容即串的模式匹配，需要掌握的是朴素算法、KMP算法及next值的求法。在考研备考中，参考严奶奶的教材，我也是在关于求next值的算法中卡了一下午时间，感觉挺有意思的，把一些思考的结果整理出来，与大家一起探讨。
3 S% x$ y4 N2 g3 _, f) Q6 y' ^

本文的逻辑顺序为
1、最基本的朴素算法
* F/ b) b& N4 H6 |2、优化的KMP算法
; R  J( G$ E: ]/ l3、应算法需要定义的next值
4、手动写出较短串的next值的方法
/ U- D" E3 b' W/ I1 A& ^7 f5、最难理解的、足足有5行的代码的求next值的算法
所有铺垫为了最后的第5点，我觉得以这个逻辑下来，由果索因还是相对好理解的，下面写的很通俗，略显不专业…
- J  a0 P3 @. B1 o$ Q  r

- }- |4 U- H7 X* C. e) j' E一、问题描述
给定一个主串S及一个模式串P，判断模式串是否为主串的子串；若是，返回匹配的第一个元素的位置（序号从1开始），否则返回0；如S=“abcd”，P=“bcd”，则返回2；S=“abcd”，P=“acb”，返回0。
7 M! w5 @/ X0 g, n' N% `

二、朴素算法
0 @3 [1 ^5 `: N: ^& Q) E' B最简单的方法及一次遍历S与P。以S=“abcabaaaabaaacac”,P="abaabcac"为例，一张动图模拟朴素算法：

. J  [$ P/ F3 r7 I5 q$ Z3 O
; a3 W% s9 b/ R! G5 J
+ q3 o' [4 ~2 Z. J4 i2 d+ V
2 `* O, k: j4 P2 K8 \! O. x& U* x. a; d这个算法简单，不多说，附上代码
. I3 W9 Y  W9 d, J. D

#include<stdio.h>
& y  y" `" w% x0 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;
5 g+ o- _& s0 M    while(i<=sLen && j<=pLen){
( a6 e' K+ ?8 U0 W4 L0 ]+ R        if(s==p[j]){i++;j++;}
        else{
            i = i-j+2;
( ~2 y3 F4 p! O( p            j = 1;
        }
    }
8 n4 z1 Y9 |- V* T% x0 I    if(j>pLen) return i-pLen;
2 {$ w' Q; @9 l( F! m    return 0;
}
void main(){
    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'};
    int sLen = sizeof(s)/sizeof(char)-1;
    int pLen = sizeof(p)/sizeof(char)-1;
    printf("%d",Index_1(s,sLen,p,pLen));
}
1
3 w8 s4 ]' o9 S5 @( C  Y  J2
: h2 N; T' u& R' L1 N1 V3 q# l5 I3
# G1 _$ `# Z+ g9 l; |5 A3 |) `0 _4
5
; s( H- D; n9 ~% R- ?9 c) [9 A) u0 w6
$ I" d+ I' I5 l# v: W) d0 H, [- y5 `7
8
9
) ]4 O" P; l  j' m10
11
) ]1 `- D/ l5 \# d: x3 O12
13
14
15
16
- J0 K* C, G' S- G17
! ]: |3 @/ ~" A18
9 p3 |; e% }; @4 n1 _3 ]  P19
20
5 R* ?5 y9 q+ _8 N. K: N* K5 [21
; I* l+ X# T3 U  `三、改进的算法——KMP算法
' w7 p& o! p' D0 H3 N! S, N8 l朴素算法理解简单，但两个串都有依次遍历，时间复杂度为O(n*m)，效率不高。由此有了KMP算法。
6 y4 B2 _" y- d3 _5 i) f. v一般的，在一次匹配中，我们是不知道主串的内容的，而模式串是我们自己定义的。
朴素算法中，P的第j位失配，默认的把P串后移一位。
但在前一轮的比较中，我们已经知道了P的前(j-1)位与S中间对应的某(j-1)个元素已经匹配成功了。这就意味着，在一轮的尝试匹配中，我们get到了主串的部分内容，我们能否利用这些内容，让P多移几位(我认为这就是KMP算法最根本的东西)，减少遍历的趟数呢？答案是肯定的。再看下面改进后的动图：

! t* q5 b  r! [, ?/ ]9 _" n
+ L7 w7 J. o( Z0 v

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


# G( F% c& e6 ~( V7 i- G相比朴素算法：
, v4 {" O- q8 f6 y4 A. ^, _朴素算法： 每次失配，S串的索引i定位的本次尝试匹配的第一个字符的后一个。P串的索引j定位到1；T(n)=O(n*m)
5 b& T3 p- r  H/ aKMP算法： 每次失配，S串的索引i不动，P串的索引j定位到某个数。T(n)=O(n+m)，时间效率明显提高
7 n+ Y6 a  Q% z

而这“定位到某个数”，这个数就是接下来引入的next值。（实际上也就是P往后移多少位，换一种说法罢了：从上图中也可以看出，失配时固定i不变，令S与P[某个数]对齐，实际上是P右移几位的另一种表达，只有为什么这么表达，当然是因为程序好写。）
* w/ [+ d& M3 G/ y, U1 [, n7 Q
6 j8 {. k4 \- ^4 b1 X
开——始——划——重——点！（图对逻辑关系比较好理解，但i和j的关系对后面求next的算法好理解！）
& [; n0 ^, e9 a9 p. V4 O

比如，Pj处失配，绿色的是Pj，则我们可以确定P1…Pj-1是与Si…Si+j-2相对应的位置一一相等的
+ M0 `3 p  Z3 Y- e- n) v/ Z

  `! Q8 C. U) t6 m: c' p$ p" c* n
假设P1…Pj-1中，P1…Pk-1与Pj-k+1…Pj-1是一一相等的，为了下面说的清楚，我们把这种关系叫做“首尾重合”


+ |9 m0 ^& c- y8 o/ H

9 U% A" ^/ U: E4 F那么可以推出，P1…Pk-1与Si…Si+j-2
  n) X& ]* ]5 ?# d
/ d1 O1 S8 L$ d+ x
( J9 z5 Q9 B  w$ M3 ^
/ d9 W$ |! Z+ \% Z+ m
显然，接下来要做的就是把模式串右移了，移到哪里就不用多说了：



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


最后，如果我们知道了一个字符串的next值，那么KMP算法也就很好懂了。相比朴素算法，当发生失配时，i不变，j=next[j]就好啦！接下来就是怎么确定next值了。
8 D- U( H5 r! B: o$ G  }: ^9 I

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

. O/ C2 s* z/ K7 ?: z# o$ ^
% t% j# U& h" Y6 ~这个扫一眼就能依次写出，会了这个方法，应付个期末考试没问题了。
( P* _3 s; q$ u0 I' D  [

, D0 v( g# ^# y8 J通过把next值“看”出来，我们再来分析next值，这就很容易得到超级有名的公式了，这个式子对后面的算法理解很重要！所以先要看懂这个式子，如果上面的内容通下来了，这个应该很容易看懂了：
* p7 h1 m, `5 O8 k; J2 a: M: U& T

# X* P" \5 Q+ y1 v; T' r

五、求next的算法
! r: }# J7 y+ M" e( n$ B' {终于到了最后了~短的串的next值我们可以“看”出来，但长的串就需要借助程序了，具体算法刚接触的时候确实不容易理解，但给我的体验，把上面的内容写完，现在感觉简简单单了…先附上程序再做解释，(终于到了传说中的整整5行代码让我整理了一下午)。
. X7 |" {) w3 C  u* v1 f

int GetNext(char ch[],int cLen,int next[]){//cLen为串ch的长度
    next[1] = 0;
    int i = 1,j = 0;
, C* G9 e# M- _% e* t7 l    while(i<=cLen){
        if(j==0||ch==ch[j]) next[++i] = ++j;
        else j = next[j];
    }
}
0 h+ B2 t3 l; P" S6 k
还是先由一般再推优化：
直接求next[j+1]（至于为什么是j+1，是为了和下面的对应）
, `& P/ D) M3 U3 }根据之前的分析，next[j+1]的值为pj+1的前j个元素的收尾重合的最大个数加一。即需要满足两个条件，把它的值一步步“检验”出来。一是“个数最多”的，因此要从可能的最大值开始验；二是“首尾重合”，因此要一一对应验是否相等。
$ Y8 H/ e, d% k3 h" H! H不难理解，next[j+1]的最大值为j，所有我们从next[j+1]=j开始“验证”。有以下优先判断顺序：
if(P1…Pj-1 == P2…Pj) => next[j+1]=j
3 ]6 a8 G* i  g# w. ]9 }5 c1 Felse if(P1…Pj-2 == P3…Pj) =>next[j+1]=j-1
, K! V' w$ @% M& v$ r7 E" Oelse if(P1…Pj-3 == P4…Pj) =>next[j+1]=j-2
…
…
8 o" y2 x/ R2 }2 n…
else if(P1P2 == Pj-1Pj) => next[j+1]=3
else if(P1 == Pj-1) => next[j+1]=2
else if(P1 != Pj-1) => next[j+1]=1
每次前去尾1个，后掐头1个，直至得到next[j+1]

8 `6 M5 Y. a; q0 ?
再进一步想，next值是一个“工具”，我们单独的求next[j+1]是完全没有意义的，就是说要求next就要把所有j的next求出来。所有一般的，我们都是已知前j个元素的next值，求next[j+1]，以此递推下去，求完整的next数组。
" Z. H, R; O* R7 f) A% \" r8 I但是，上面的思考过程还是最根本的。所以问题变为两个：知道前j个元素的next的情况下，
①next[j+1]的可能的最大值是多少（即从哪开始验证）
& a4 {, H; T1 L/ L# ?# y" H5 C②某一步验证失败后，需要“前去尾几个，后掐头几个？”（即本次验证失败后，再验证哪个值）
1 j. C/ I1 W( ^9 a看一下的分析：
1 K+ v4 y% }2 b$ O1 C; }/ u) _) E

1、next[j+1]的最大值为next[j]+1。
因为：
# u0 b8 q& @  p. u1 x假设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
8 g( D1 m6 W) h( G- x2、如果Pk1≠Pj，那么next[j+1]可能的次大值为next[next[j]]+1，以此类推即可高效求出next[j+1]
! y2 l. p; k$ P, V1 y/ q  b! r这里不好解释，直接看下面的流程分析及图解


3 w6 M: o: i: s& a开——始——划——重——点！
从头走一遍流程
! r/ s# @. f7 C7 v4 B①求next[j+1]，设值为m
②已知next[j]=k1，则有P1…Pk1-1 = Pj-k1+1…Pj-1
6 }3 n) |( g9 S  E7 i$ e* `③如果Pk1=Pj，则P1…Pk1-1PK = Pj-k1+1…Pj-1Pj，则next[j+1]=k1+1，否则
④已知next[k1]=k2，则有P1…Pk2-1 = Pk1-k2+1…Pk1-1
% U1 J% `( p; N' \( r* v9 Z  d6 d⑤第二第三步联合得到:
! J+ Q( w$ m* R/ [! T. j) [P1…Pk2-1 = Pk1-k2+1…Pk1-1 = Pj-k1+1…Pk2-k1+j-1 = Pj-k2+1…Pj-1 即四段重合
⑥这时候，再判断如果Pk2=Pj，则P1…Pk2-1P~k2 = Pj-k2+1…Pj-1Pj，则next[j+1]=k2+1；否则再取next[k2]=k3…以此类推
5 \5 P5 v) G; o& |5 S+ J. P
/ J; a4 h! _" d/ m! l
上面几步，耐心看下来，结合那个式子很容易看懂。最后，再加一个图的模拟帮助理解：
1、要求next[k+1] 其中k+1=17
, W' \4 g6 Z( r

- r: K. V3 `! D( L; O  r2、已知next[16]=8，则元素有以下关系：
/ t' ]; J5 a) A% h  S6 Q1 M9 x  L
! y- R8 u6 m7 }) _0 N( r, f
9 i2 ^/ e% ^9 v0 g1 J3、如果P8=P16，则明显next[17]=8+1=9
  q9 b' s3 x# Y, U1 q4、如果不相等，又若next[8]=4，则有以下关系
+ V! I, c6 m4 q" y2 D$ m

又加上2的条件知
% @- f7 |  s. R* J; g, Q7 v5 V- L

主要是为了证明：
  _' I; Z' n" c9 ]; S/ `* ?6 ]

! K& c+ y7 N9 R6 |$ X5、现在在判断，如果P16=P4则next[17]=4+1=5，否则，在继续递推
6、若next[4]=2，则有以下关系

+ n0 s5 Q$ d) A( q# m+ u  f
7、若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版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_37969433/article/details/82947411
& ^3 g8 P: c! r
- K9 o! |: D2 Q! v0 g0 N+ ~6 E
6 h' J) t' q& U) P