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

杨利霞

（算法）通俗易懂的字符串匹配KMP算法及求next值算法
5 ]6 b3 k" N; t7 \
3 K" m* L: Q! S6 A% Y) V大多数据结构课本中，串涉及的内容即串的模式匹配，需要掌握的是朴素算法、KMP算法及next值的求法。在考研备考中，参考严奶奶的教材，我也是在关于求next值的算法中卡了一下午时间，感觉挺有意思的，把一些思考的结果整理出来，与大家一起探讨。


, v. N- n, [2 f' v3 M4 c本文的逻辑顺序为
1、最基本的朴素算法
! J8 [6 }% S% V) _, p. {2、优化的KMP算法
7 k5 q; h0 l7 L4 j  [& {3、应算法需要定义的next值
. ?/ R) a% n3 o$ Y: d4、手动写出较短串的next值的方法
4 x" t5 C* v% v. ]- z5、最难理解的、足足有5行的代码的求next值的算法
+ |" C% N# z5 @3 X# j所有铺垫为了最后的第5点，我觉得以这个逻辑下来，由果索因还是相对好理解的，下面写的很通俗，略显不专业…
# r% i2 }/ ]8 J2 a6 R

  n* C( B" |3 n, n/ R/ o! G一、问题描述
, [1 r$ }9 ~3 {3 `0 f: V9 b给定一个主串S及一个模式串P，判断模式串是否为主串的子串；若是，返回匹配的第一个元素的位置（序号从1开始），否则返回0；如S=“abcd”，P=“bcd”，则返回2；S=“abcd”，P=“acb”，返回0。

' i. M" o% P+ K9 Q4 ^5 @9 @1 L
二、朴素算法
最简单的方法及一次遍历S与P。以S=“abcabaaaabaaacac”,P="abaabcac"为例，一张动图模拟朴素算法：
- W' d3 c) ^0 m0 ~, I



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

8 X8 \6 N( U4 G% B  T- t
# r. ]; ]; ]4 m1 n% S! b#include<stdio.h>
int Index_1(char s[],int sLen,char p[],int pLen){//s为主串，sLen为主串元素个数，p为模式串，pLen为模式串的个数
, m) T; A9 F* ?, N  k. w7 y    if(sLen<pLen)return 0;
8 K% m# A. j4 `. N4 p7 d    int i = 1,j = 1;
    while(i<=sLen && j<=pLen){
        if(s==p[j]){i++;j++;}
        else{
8 e  m- w' g4 r# h            i = i-j+2;
) Q9 l3 C" K6 Q3 Y; Z            j = 1;
. g% x" C- p/ y) B: N3 B$ L        }
    }
6 s! ^' ^+ l: e    if(j>pLen) return i-pLen;
$ C; S( g( |  A& L/ v    return 0;
& ?! g8 k5 M* i/ y5 M- v}
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));
}
$ b6 b, x5 |1 |4 k" h  }1
2
3
. A9 K) V8 O; C$ X' ]4
5
7 x; |+ g7 {- v) N* o1 e; C% b6 u6
4 A4 P* ?  k( v3 g7
2 T6 p0 j/ `: X& x6 ]% ~5 }; f3 T5 C8
9
# M7 o: @% v' b7 x( s& L# n10
( b6 h1 V7 Z  r; L$ m& r. R. {11
0 S# U: _, d2 F0 {6 ^12
7 i; D" y- O6 i' f13
14
15
  q- U/ ]2 ?7 R! l# _16
17
6 r* ^, \% p6 _' g3 b18
( E/ G- K  j; P/ e2 q: m+ Q. l19
20
21
# }5 M" Y# x3 @5 Y4 ~. ~* ~' D- m* n三、改进的算法——KMP算法
" D8 X( e" h+ f  ~: U0 R3 |朴素算法理解简单，但两个串都有依次遍历，时间复杂度为O(n*m)，效率不高。由此有了KMP算法。
4 g, X: J: S* H2 i一般的，在一次匹配中，我们是不知道主串的内容的，而模式串是我们自己定义的。
朴素算法中，P的第j位失配，默认的把P串后移一位。
但在前一轮的比较中，我们已经知道了P的前(j-1)位与S中间对应的某(j-1)个元素已经匹配成功了。这就意味着，在一轮的尝试匹配中，我们get到了主串的部分内容，我们能否利用这些内容，让P多移几位(我认为这就是KMP算法最根本的东西)，减少遍历的趟数呢？答案是肯定的。再看下面改进后的动图：

1 d7 ]9 c$ d" e" x$ e  j
" I6 t5 }+ B, ]0 P& x7 d

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


相比朴素算法：
3 p1 o. s. r/ J: r9 _& e朴素算法： 每次失配，S串的索引i定位的本次尝试匹配的第一个字符的后一个。P串的索引j定位到1；T(n)=O(n*m)
" V! w6 j! D4 f2 l  ^KMP算法： 每次失配，S串的索引i不动，P串的索引j定位到某个数。T(n)=O(n+m)，时间效率明显提高

- _9 Z, w4 |/ Y  v0 h! Z: Q; {9 ~1 ~
4 u! L% w; O% d. r1 U# @9 v而这“定位到某个数”，这个数就是接下来引入的next值。（实际上也就是P往后移多少位，换一种说法罢了：从上图中也可以看出，失配时固定i不变，令S与P[某个数]对齐，实际上是P右移几位的另一种表达，只有为什么这么表达，当然是因为程序好写。）


开——始——划——重——点！（图对逻辑关系比较好理解，但i和j的关系对后面求next的算法好理解！）
- g# d+ T9 J# ?2 ?. V# P" [* K, k
5 U; B4 C$ v9 ~" C* A  i
/ V5 W7 R2 ^$ D5 g# t' P; B比如，Pj处失配，绿色的是Pj，则我们可以确定P1…Pj-1是与Si…Si+j-2相对应的位置一一相等的
  _6 V. v. f4 \7 B
+ x& {& n$ h# j* N* e

假设P1…Pj-1中，P1…Pk-1与Pj-k+1…Pj-1是一一相等的，为了下面说的清楚，我们把这种关系叫做“首尾重合”
- h. E( ~- O7 a
' v& Q' ]  b+ T


) V! H  y$ \; ]' f! N那么可以推出，P1…Pk-1与Si…Si+j-2
4 l9 C' I2 E+ ]5 [8 }


& s3 }- e' L+ ~6 d4 J
' x% O5 d1 o# I) g显然，接下来要做的就是把模式串右移了，移到哪里就不用多说了：
4 d. S) t7 F. ~4 M

* K/ P1 {7 N8 ]  \
) X% s' g+ ?1 N2 i1 P9 e
. G3 X6 u, @% C4 S. k5 F为了表示下一轮比较j定位的地方，我们将其定义为next[j]，next[j]就是第j个元素前j-1个元素首尾重合部分个数加一，当然，为了能遍历完整，首尾重合部分的元素个数应取到最多，即next[j]应取尽量大的值，原因挺好理解的，可以想个例子模拟一下，会完美跳过正确结果。在上图中就是绿色元素的next值为蓝色元素的序号。也即，对于字符串P，next[8]=4。如此，再看一下上面的动图是不是清楚了不少。

1 B8 B( e) j& H; d* _$ V  r. G
3 p3 _+ J' P; b/ Q4 G( T$ q, s3 ~最后，如果我们知道了一个字符串的next值，那么KMP算法也就很好懂了。相比朴素算法，当发生失配时，i不变，j=next[j]就好啦！接下来就是怎么确定next值了。

  G) f2 T* S6 Z; G
四、手动写出一个串的next值
我们规定任何一个串，next[1]=0。(不用next[0]，与串的所有对应)，仍是一张动图搞定问题：
3 {6 i" Q- ^8 s! i! A" x" i; a
- Q( c3 j$ E. I" \+ p
这个扫一眼就能依次写出，会了这个方法，应付个期末考试没问题了。

* \  Q8 u' x. E( v3 J9 @% l3 C
通过把next值“看”出来，我们再来分析next值，这就很容易得到超级有名的公式了，这个式子对后面的算法理解很重要！所以先要看懂这个式子，如果上面的内容通下来了，这个应该很容易看懂了：


' K& _) P( ?- w- [

, t( e- w# Z0 x1 j& G: D五、求next的算法
5 z- r) p4 G, G9 A终于到了最后了~短的串的next值我们可以“看”出来，但长的串就需要借助程序了，具体算法刚接触的时候确实不容易理解，但给我的体验，把上面的内容写完，现在感觉简简单单了…先附上程序再做解释，(终于到了传说中的整整5行代码让我整理了一下午)。
  s! s5 e9 P% H7 [8 {
) h5 [" d  v& R
# t; x7 Z6 I- i# C- D! a" p/ @int GetNext(char ch[],int cLen,int next[]){//cLen为串ch的长度
    next[1] = 0;
    int i = 1,j = 0;
1 J$ y: |$ r; D1 _9 N2 ~    while(i<=cLen){
9 q( |/ O( l2 O# B6 C/ Z        if(j==0||ch==ch[j]) next[++i] = ++j;
) {7 w2 P9 u0 Y4 L0 m: w" l) _        else j = next[j];
    }
1 ?' }6 g9 D" y8 F}

还是先由一般再推优化：
直接求next[j+1]（至于为什么是j+1，是为了和下面的对应）
根据之前的分析，next[j+1]的值为pj+1的前j个元素的收尾重合的最大个数加一。即需要满足两个条件，把它的值一步步“检验”出来。一是“个数最多”的，因此要从可能的最大值开始验；二是“首尾重合”，因此要一一对应验是否相等。
8 y- C6 \, N7 |  H不难理解，next[j+1]的最大值为j，所有我们从next[j+1]=j开始“验证”。有以下优先判断顺序：
6 n# N) A  `3 O0 Xif(P1…Pj-1 == P2…Pj) => next[j+1]=j
else if(P1…Pj-2 == P3…Pj) =>next[j+1]=j-1
else if(P1…Pj-3 == P4…Pj) =>next[j+1]=j-2
- [1 V5 Y# S4 y2 h& u…
…
) u! x! K! Y* J" ?7 N- l! h…
6 V4 {' ~( n5 j, q7 N2 Celse if(P1P2 == Pj-1Pj) => next[j+1]=3
0 f, o; r6 ]  belse if(P1 == Pj-1) => next[j+1]=2
else if(P1 != Pj-1) => next[j+1]=1
每次前去尾1个，后掐头1个，直至得到next[j+1]
/ X, K1 Y$ O% W

7 t, u! ?5 ^8 Q/ o再进一步想，next值是一个“工具”，我们单独的求next[j+1]是完全没有意义的，就是说要求next就要把所有j的next求出来。所有一般的，我们都是已知前j个元素的next值，求next[j+1]，以此递推下去，求完整的next数组。
* ?8 Y- x% U9 v! G但是，上面的思考过程还是最根本的。所以问题变为两个：知道前j个元素的next的情况下，
①next[j+1]的可能的最大值是多少（即从哪开始验证）
, E4 d8 W/ A) J4 t5 W# p" k②某一步验证失败后，需要“前去尾几个，后掐头几个？”（即本次验证失败后，再验证哪个值）
8 Z" }* [: v7 `看一下的分析：

  N& M1 d# w- U- W7 h' J5 G% l
1、next[j+1]的最大值为next[j]+1。
4 T; G; k) B$ l1 M! Y因为：
* T8 s; Y/ y0 }/ B0 q$ T/ e1 ?7 t假设next[j]=k1，则可以说明P1…Pk1-1=Pj-k1+1…Pj-1，且这是前j个元素最大的首尾重合序列。
0 \, R) W1 S7 C5 ?* d! d# Q7 X& w如果Pk1=Pj，那么P1…Pk1-1PK=Pj-k1+1…Pj-1Pj，那么k+1这也是前j+1个元素的最大首尾重合序列，也即next[j+1]的值为k1+1
* d6 M& e6 X# }6 B; b2、如果Pk1≠Pj，那么next[j+1]可能的次大值为next[next[j]]+1，以此类推即可高效求出next[j+1]
这里不好解释，直接看下面的流程分析及图解
; ]+ A; d; [" n7 U6 b5 r/ ~: a- a

5 y! Q' ^+ r# y. y) |+ o! i开——始——划——重——点！
8 g' M9 W7 k2 r' \2 s( p从头走一遍流程
: s! O# V* Q. f6 b①求next[j+1]，设值为m
4 A6 s* J. \, @' \' \②已知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，否则
④已知next[k1]=k2，则有P1…Pk2-1 = Pk1-k2+1…Pk1-1
  g/ t8 V# @6 c8 n⑤第二第三步联合得到:
0 k' u, f) J$ Q/ m8 S; nP1…Pk2-1 = Pk1-k2+1…Pk1-1 = Pj-k1+1…Pk2-k1+j-1 = Pj-k2+1…Pj-1 即四段重合
' T$ u* h1 C* j# E7 {⑥这时候，再判断如果Pk2=Pj，则P1…Pk2-1P~k2 = Pj-k2+1…Pj-1Pj，则next[j+1]=k2+1；否则再取next[k2]=k3…以此类推
& y$ q9 `: [2 o) s3 `. ^

上面几步，耐心看下来，结合那个式子很容易看懂。最后，再加一个图的模拟帮助理解：
1、要求next[k+1] 其中k+1=17


2、已知next[16]=8，则元素有以下关系：
# d+ H/ v8 p% r

7 v- ^6 i1 h$ L( M$ H0 Z3、如果P8=P16，则明显next[17]=8+1=9
) @% C# |, H. _. D3 N4、如果不相等，又若next[8]=4，则有以下关系


7 h1 p3 G( M% ~$ [又加上2的条件知
; \& a' W" o0 x1 g; `' H

主要是为了证明：


! b4 e( n' t; J% s* B, M6 B* w" K5、现在在判断，如果P16=P4则next[17]=4+1=5，否则，在继续递推
0 z4 ~5 ?+ E" t6 b* V& L1 P* e6、若next[4]=2，则有以下关系


3 m' g. M+ \" q( e: M6 {7、若P16=P2，则next[17]=2+1=3;否则继续取next[2]=1、next[1]=0；遇到0时还没出结果，则递推结束，此时next[17]=1。最后，再返回看那5行算法，应该很容易明白了！
————————————————
  Z% d) ~1 I* V* M1 P, ^版权声明：本文为CSDN博主「Sirm23333」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_37969433/article/details/82947411
, X8 ~- R+ q$ m* n

& |, I  r4 p( _! r
6 P- ^( A! I! i, y