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

杨利霞

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

3 X% |! r# O* R. D1 T大多数据结构课本中，串涉及的内容即串的模式匹配，需要掌握的是朴素算法、KMP算法及next值的求法。在考研备考中，参考严奶奶的教材，我也是在关于求next值的算法中卡了一下午时间，感觉挺有意思的，把一些思考的结果整理出来，与大家一起探讨。


( z: A4 }  M# \5 l9 c本文的逻辑顺序为
1、最基本的朴素算法
2、优化的KMP算法
: }/ I/ x; f* O2 j% b$ y; J3、应算法需要定义的next值
4、手动写出较短串的next值的方法
/ {% P, U6 F; E) G5、最难理解的、足足有5行的代码的求next值的算法
) u9 T" g3 C$ R5 d" t4 \, m% ^6 r6 f所有铺垫为了最后的第5点，我觉得以这个逻辑下来，由果索因还是相对好理解的，下面写的很通俗，略显不专业…

. g& U, R0 B. ^7 ?
7 i% D4 e2 z8 |- h- t! z一、问题描述
9 S+ e1 C1 p, S给定一个主串S及一个模式串P，判断模式串是否为主串的子串；若是，返回匹配的第一个元素的位置（序号从1开始），否则返回0；如S=“abcd”，P=“bcd”，则返回2；S=“abcd”，P=“acb”，返回0。


4 l/ T7 P$ m- _8 g7 d二、朴素算法
最简单的方法及一次遍历S与P。以S=“abcabaaaabaaacac”,P="abaabcac"为例，一张动图模拟朴素算法：
, }) b, x8 t1 M+ K( |2 g8 D

* p2 h3 Q  m* ?* g7 f7 O2 B( s) T
* F# f$ c& i6 U) ]1 z! t
' S/ e. F' W' P" {+ `6 Z! a这个算法简单，不多说，附上代码

% g/ Y8 K0 s) `1 H* }
" H0 [- v) r2 p: D' m& D; b#include<stdio.h>
int 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){
        if(s==p[j]){i++;j++;}
% b& b! P% I$ ~  \' R0 g6 D        else{
            i = i-j+2;
            j = 1;
! O8 G0 A  H- d& Y4 z! o5 s        }
    }
! C( H0 q6 i* z9 b% ~    if(j>pLen) return i-pLen;
$ ~9 b  |  ]: i1 C, p" n  e    return 0;
}
void main(){
4 m( p- I: j  L8 d; R* X    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'};
0 s* a9 G: J1 ]9 j) {7 Z    int sLen = sizeof(s)/sizeof(char)-1;
    int pLen = sizeof(p)/sizeof(char)-1;
    printf("%d",Index_1(s,sLen,p,pLen));
6 t/ {$ \* Z4 z4 j6 O/ O}
1
2
, A* E) R  L6 g8 M3
4
$ l; n4 W& m" ~  V, B8 M5
6
7
5 i, ]% a7 ~$ Y! y% e* D8
9
$ w* W- c% T+ l, Z6 V- C4 }. i10
11
12
13
! V3 Z" s) J* H14
15
16
9 S8 d. `5 J9 E$ C3 c6 A/ j) r1 C17
18
! c  `: x# i* {5 d19
20
21
三、改进的算法——KMP算法
+ |0 `9 O, G6 f6 W' b朴素算法理解简单，但两个串都有依次遍历，时间复杂度为O(n*m)，效率不高。由此有了KMP算法。
; ^# i; w* p+ _) }+ S一般的，在一次匹配中，我们是不知道主串的内容的，而模式串是我们自己定义的。
朴素算法中，P的第j位失配，默认的把P串后移一位。
但在前一轮的比较中，我们已经知道了P的前(j-1)位与S中间对应的某(j-1)个元素已经匹配成功了。这就意味着，在一轮的尝试匹配中，我们get到了主串的部分内容，我们能否利用这些内容，让P多移几位(我认为这就是KMP算法最根本的东西)，减少遍历的趟数呢？答案是肯定的。再看下面改进后的动图：

: s8 s2 B) P8 [3 C

* m! |4 ?9 d; S
2 V, A. ^* W7 G1 t这个模拟过程即KMP算法，若没有看明白，继续往下看相应的解释，理解需要把P多移几位，然后回头再看一遍这个图就很明了了。
3 x% h8 r1 M& G8 r1 y( m
( ^( u' s( h9 f9 T6 Z. a0 U8 D
% N5 a. K* ^- \. ^相比朴素算法：
3 ~* S6 T5 X: I0 K1 s! q朴素算法： 每次失配，S串的索引i定位的本次尝试匹配的第一个字符的后一个。P串的索引j定位到1；T(n)=O(n*m)
KMP算法： 每次失配，S串的索引i不动，P串的索引j定位到某个数。T(n)=O(n+m)，时间效率明显提高
% r8 `6 B, M" m( K

而这“定位到某个数”，这个数就是接下来引入的next值。（实际上也就是P往后移多少位，换一种说法罢了：从上图中也可以看出，失配时固定i不变，令S与P[某个数]对齐，实际上是P右移几位的另一种表达，只有为什么这么表达，当然是因为程序好写。）
6 j! s! G8 Q& Q! c3 O; c) s
3 I. Z1 I/ Z9 I2 ?( [5 D
: w9 P+ x* |# x# O9 B! |开——始——划——重——点！（图对逻辑关系比较好理解，但i和j的关系对后面求next的算法好理解！）

* y. g2 N( r* e0 ]
+ C8 C- _5 F: c$ O2 m" S$ \8 M比如，Pj处失配，绿色的是Pj，则我们可以确定P1…Pj-1是与Si…Si+j-2相对应的位置一一相等的
/ t+ F7 A! j! P6 _+ q

- X, Z; }$ Z; X. H% O2 e2 y" d
假设P1…Pj-1中，P1…Pk-1与Pj-k+1…Pj-1是一一相等的，为了下面说的清楚，我们把这种关系叫做“首尾重合”
6 X; Z8 s- ^: n8 A: o+ W& v3 S


; R3 A- A* i9 J3 O7 ~: d) ?
6 i9 m; ?, E% c; A. X6 m那么可以推出，P1…Pk-1与Si…Si+j-2
. u. J; U- p+ s: J


$ {; q8 `2 C) L2 V
显然，接下来要做的就是把模式串右移了，移到哪里就不用多说了：
# L$ K. e2 u& c) a9 X
. Q) p& k. b* f$ h3 d' Y
+ ?. C; K" L/ X9 G2 g

) \/ L/ Z" [" }为了表示下一轮比较j定位的地方，我们将其定义为next[j]，next[j]就是第j个元素前j-1个元素首尾重合部分个数加一，当然，为了能遍历完整，首尾重合部分的元素个数应取到最多，即next[j]应取尽量大的值，原因挺好理解的，可以想个例子模拟一下，会完美跳过正确结果。在上图中就是绿色元素的next值为蓝色元素的序号。也即，对于字符串P，next[8]=4。如此，再看一下上面的动图是不是清楚了不少。
/ S" `2 |3 f5 ], y$ U/ T: d

最后，如果我们知道了一个字符串的next值，那么KMP算法也就很好懂了。相比朴素算法，当发生失配时，i不变，j=next[j]就好啦！接下来就是怎么确定next值了。
/ v' Y/ H8 \; ~$ V+ j& i
1 V$ L& v2 b# }. J4 i9 R0 L( X0 l
1 F& u  K5 \! q5 N* m/ _四、手动写出一个串的next值
我们规定任何一个串，next[1]=0。(不用next[0]，与串的所有对应)，仍是一张动图搞定问题：
# w8 W5 i7 ?# X+ s& N4 T% }
# h! y! i" a# {, Q
) g9 u# R) ^' E- X这个扫一眼就能依次写出，会了这个方法，应付个期末考试没问题了。
4 D: }. B: _0 L' B1 @5 x
, ?5 o& j# t. ]1 a8 r- a0 _
通过把next值“看”出来，我们再来分析next值，这就很容易得到超级有名的公式了，这个式子对后面的算法理解很重要！所以先要看懂这个式子，如果上面的内容通下来了，这个应该很容易看懂了：
1 j3 z8 g! Z+ N



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

5 `( H; x2 X/ a& E# k$ ]) H3 y
int GetNext(char ch[],int cLen,int next[]){//cLen为串ch的长度
4 M0 l3 x9 D" v    next[1] = 0;
4 h5 E; g( r! H) Z    int i = 1,j = 0;
. O' G/ D& {* z: ]6 T7 W! |( V    while(i<=cLen){
/ N2 l6 H. t) s, x/ f        if(j==0||ch==ch[j]) next[++i] = ++j;
        else j = next[j];
    }
6 m7 U+ s9 Z& J2 h: U}

还是先由一般再推优化：
直接求next[j+1]（至于为什么是j+1，是为了和下面的对应）
6 n6 @' g% S8 O6 p, S4 W% ^3 ^根据之前的分析，next[j+1]的值为pj+1的前j个元素的收尾重合的最大个数加一。即需要满足两个条件，把它的值一步步“检验”出来。一是“个数最多”的，因此要从可能的最大值开始验；二是“首尾重合”，因此要一一对应验是否相等。
不难理解，next[j+1]的最大值为j，所有我们从next[j+1]=j开始“验证”。有以下优先判断顺序：
& m, d" s) M& O$ {5 s9 A/ yif(P1…Pj-1 == P2…Pj) => next[j+1]=j
! ?# m0 f; T  t2 K1 [5 Relse if(P1…Pj-2 == P3…Pj) =>next[j+1]=j-1
else if(P1…Pj-3 == P4…Pj) =>next[j+1]=j-2
…
, i8 P4 f1 v0 v5 J: ]…
…
else if(P1P2 == Pj-1Pj) => next[j+1]=3
else if(P1 == Pj-1) => next[j+1]=2
# y" W  L% S5 L  P' velse if(P1 != Pj-1) => next[j+1]=1
! S( r+ W; c8 {) d  K; [) Z. l- y8 [每次前去尾1个，后掐头1个，直至得到next[j+1]


9 |, g; e- u- y再进一步想，next值是一个“工具”，我们单独的求next[j+1]是完全没有意义的，就是说要求next就要把所有j的next求出来。所有一般的，我们都是已知前j个元素的next值，求next[j+1]，以此递推下去，求完整的next数组。
( E3 v1 O' [) x* H7 m2 _但是，上面的思考过程还是最根本的。所以问题变为两个：知道前j个元素的next的情况下，
①next[j+1]的可能的最大值是多少（即从哪开始验证）
②某一步验证失败后，需要“前去尾几个，后掐头几个？”（即本次验证失败后，再验证哪个值）
看一下的分析：
1 w( Y9 {) a. }0 r  a7 X9 `$ u
( ]  u! g: ^2 y2 |  E" P
1、next[j+1]的最大值为next[j]+1。
因为：
: i6 b) |& S/ J2 a8 S9 N假设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
2、如果Pk1≠Pj，那么next[j+1]可能的次大值为next[next[j]]+1，以此类推即可高效求出next[j+1]
这里不好解释，直接看下面的流程分析及图解

6 e( A0 d! U% H5 S1 C+ e4 {
1 T) k7 O1 c! E, Y开——始——划——重——点！
0 c. g6 ^- g- Y从头走一遍流程
①求next[j+1]，设值为m
8 X/ p! a! Z! X- D! O②已知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
9 V) B: Z8 k, I* n% }- d⑤第二第三步联合得到:
4 j; _" P3 v4 F' UP1…Pk2-1 = Pk1-k2+1…Pk1-1 = Pj-k1+1…Pk2-k1+j-1 = Pj-k2+1…Pj-1 即四段重合
# S8 `( E* ^4 b* o⑥这时候，再判断如果Pk2=Pj，则P1…Pk2-1P~k2 = Pj-k2+1…Pj-1Pj，则next[j+1]=k2+1；否则再取next[k2]=k3…以此类推
  T: Y$ L3 d5 _- W& p3 i9 S

; G4 L  f: |% D3 g' @3 G; v- k上面几步，耐心看下来，结合那个式子很容易看懂。最后，再加一个图的模拟帮助理解：
1、要求next[k+1] 其中k+1=17

* s& e! {4 U- o8 O. ]: }5 p
2、已知next[16]=8，则元素有以下关系：
% q7 W8 N/ m/ K/ w- E
3 B- t$ W8 |+ R2 q6 d
* f6 j6 G: Q& `: W9 [3、如果P8=P16，则明显next[17]=8+1=9
9 _  I/ n" m. A. t. k5 i% A, s4、如果不相等，又若next[8]=4，则有以下关系
; g9 t3 p* F6 M
$ k4 ]6 j" n8 _" K1 \
又加上2的条件知


主要是为了证明：

+ B+ g9 G2 X6 e( k
1 p1 I/ R( @  f, M/ a0 {! }- B5、现在在判断，如果P16=P4则next[17]=4+1=5，否则，在继续递推
6、若next[4]=2，则有以下关系
! x4 G( j  J9 ]# A" l
, v4 n+ B5 ?- Y8 R8 a! f6 |1 k2 ]# Z( r
7、若P16=P2，则next[17]=2+1=3;否则继续取next[2]=1、next[1]=0；遇到0时还没出结果，则递推结束，此时next[17]=1。最后，再返回看那5行算法，应该很容易明白了！
/ A# H* r# Y/ g  e% i————————————————
( m: L# H0 \7 l( T4 E* _: T版权声明：本文为CSDN博主「Sirm23333」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_37969433/article/details/82947411
0 L+ q& e- G1 ~: B+ _/ ^
- q# `, J  N1 ?  M. ?