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

杨利霞

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

大多数据结构课本中，串涉及的内容即串的模式匹配，需要掌握的是朴素算法、KMP算法及next值的求法。在考研备考中，参考严奶奶的教材，我也是在关于求next值的算法中卡了一下午时间，感觉挺有意思的，把一些思考的结果整理出来，与大家一起探讨。
9 @( Y8 f3 K- O" k4 I

本文的逻辑顺序为
) u. i# |' G! m4 T7 f; Q1、最基本的朴素算法
9 A3 ?! d0 X7 s2、优化的KMP算法
3、应算法需要定义的next值
4、手动写出较短串的next值的方法
5、最难理解的、足足有5行的代码的求next值的算法
所有铺垫为了最后的第5点，我觉得以这个逻辑下来，由果索因还是相对好理解的，下面写的很通俗，略显不专业…


一、问题描述
给定一个主串S及一个模式串P，判断模式串是否为主串的子串；若是，返回匹配的第一个元素的位置（序号从1开始），否则返回0；如S=“abcd”，P=“bcd”，则返回2；S=“abcd”，P=“acb”，返回0。
+ g5 J1 G+ |6 p& N. c4 [& i6 {, E4 a7 W

; a3 ?5 F2 x8 [# S" \二、朴素算法
最简单的方法及一次遍历S与P。以S=“abcabaaaabaaacac”,P="abaabcac"为例，一张动图模拟朴素算法：


8 W+ N' F' w, p# h% X0 v
0 h3 B% e3 W6 B4 a& I2 z  d% W
9 O' V8 b* W5 Z5 M" c这个算法简单，不多说，附上代码

; b2 |4 I0 e5 O$ r/ X
1 k) b1 _5 a  q  p. t- y#include<stdio.h>
- ^: {1 `' M2 r+ p# G8 z  x6 s# n! qint 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++;}
        else{
9 _% {9 Y1 A; e1 @  M; O            i = i-j+2;
            j = 1;
# C; {3 q5 a( Z; ^2 r. u5 q# h2 x        }
    }
" c; [2 M& @3 I    if(j>pLen) return i-pLen;
: C3 O) {$ C0 f, }( R/ z) p    return 0;
}
& l8 F/ `# p% B% D" f: q5 bvoid 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'};
& E( w0 n; }- P! m: \) u) Z+ Y# B    int sLen = sizeof(s)/sizeof(char)-1;
    int pLen = sizeof(p)/sizeof(char)-1;
    printf("%d",Index_1(s,sLen,p,pLen));
}
1
2
3
4
5
5 c# p+ D) T3 V. R& V' A6
7
0 U% F, R4 R0 z& G- S' y+ d7 {6 d9 f8
9
$ r$ c; r/ k6 K- J10
11
" A) U2 i. p/ t3 ?2 [$ ~3 B( T12
13
14
15
16
7 \7 Q; O, ~) ^5 s( g+ u# u17
18
% Q4 h+ u' q( m19
* J: T  M9 w; \" Y. f9 i) P20
21
  g" _0 \8 X+ E  [三、改进的算法——KMP算法
, X6 Y% {9 z( \, O& W! F朴素算法理解简单，但两个串都有依次遍历，时间复杂度为O(n*m)，效率不高。由此有了KMP算法。
一般的，在一次匹配中，我们是不知道主串的内容的，而模式串是我们自己定义的。
# m( `1 D5 M4 `9 n8 y朴素算法中，P的第j位失配，默认的把P串后移一位。
但在前一轮的比较中，我们已经知道了P的前(j-1)位与S中间对应的某(j-1)个元素已经匹配成功了。这就意味着，在一轮的尝试匹配中，我们get到了主串的部分内容，我们能否利用这些内容，让P多移几位(我认为这就是KMP算法最根本的东西)，减少遍历的趟数呢？答案是肯定的。再看下面改进后的动图：
) \* A- Q' p" P' T/ r- k* r
& [* K6 F( k. a


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


( c1 e0 p: m, J. O相比朴素算法：
9 _9 n% j( Z1 V1 c  x# E  p朴素算法： 每次失配，S串的索引i定位的本次尝试匹配的第一个字符的后一个。P串的索引j定位到1；T(n)=O(n*m)
5 M  s  A( R. OKMP算法： 每次失配，S串的索引i不动，P串的索引j定位到某个数。T(n)=O(n+m)，时间效率明显提高
' r0 ]5 Z+ f% T) i' \
; S/ V0 L" F) M1 A$ |" T' J
而这“定位到某个数”，这个数就是接下来引入的next值。（实际上也就是P往后移多少位，换一种说法罢了：从上图中也可以看出，失配时固定i不变，令S与P[某个数]对齐，实际上是P右移几位的另一种表达，只有为什么这么表达，当然是因为程序好写。）


% v) x% U$ E& y; ?开——始——划——重——点！（图对逻辑关系比较好理解，但i和j的关系对后面求next的算法好理解！）
/ R& W0 z4 G2 ^5 g( o9 }& W
: K+ X9 _- m7 L) [6 O
+ {; ~5 A# e  [* N, T& C比如，Pj处失配，绿色的是Pj，则我们可以确定P1…Pj-1是与Si…Si+j-2相对应的位置一一相等的


6 R2 f7 w0 Y: M: u. d  j' l
假设P1…Pj-1中，P1…Pk-1与Pj-k+1…Pj-1是一一相等的，为了下面说的清楚，我们把这种关系叫做“首尾重合”
# H. Y9 i  E1 B) R6 x6 _9 C

1 E$ h& w# z( A* `) D( p
2 Z' b) r% \7 m! i
那么可以推出，P1…Pk-1与Si…Si+j-2


/ ^# }' J; m7 P. r! [
5 G2 f3 C! W7 L( |7 U& ]% Y
显然，接下来要做的就是把模式串右移了，移到哪里就不用多说了：

* P; m3 h  F* L3 i5 k) {" ?: f* `6 \
# N, C5 E. R' r1 z
- ]3 D0 r; ]! h* z9 B" a
  F, ?4 q% b$ L# S6 z为了表示下一轮比较j定位的地方，我们将其定义为next[j]，next[j]就是第j个元素前j-1个元素首尾重合部分个数加一，当然，为了能遍历完整，首尾重合部分的元素个数应取到最多，即next[j]应取尽量大的值，原因挺好理解的，可以想个例子模拟一下，会完美跳过正确结果。在上图中就是绿色元素的next值为蓝色元素的序号。也即，对于字符串P，next[8]=4。如此，再看一下上面的动图是不是清楚了不少。


最后，如果我们知道了一个字符串的next值，那么KMP算法也就很好懂了。相比朴素算法，当发生失配时，i不变，j=next[j]就好啦！接下来就是怎么确定next值了。
- S. |$ H% u$ U5 Y

$ U3 z5 Q2 V! ?4 K0 ^/ a' J四、手动写出一个串的next值
9 m  m% D# f: `5 b8 t, _我们规定任何一个串，next[1]=0。(不用next[0]，与串的所有对应)，仍是一张动图搞定问题：


# f2 M! b: S' Z2 [( h) s5 D这个扫一眼就能依次写出，会了这个方法，应付个期末考试没问题了。
; g* m0 b9 I1 W8 Y

: E4 M% `4 f8 q* u; O* a通过把next值“看”出来，我们再来分析next值，这就很容易得到超级有名的公式了，这个式子对后面的算法理解很重要！所以先要看懂这个式子，如果上面的内容通下来了，这个应该很容易看懂了：


; N( Y$ M) k, \1 w' @. O4 h* z
1 ]# R& h  B1 D7 m6 t- B, D
% _' A7 F8 j6 v% T五、求next的算法
$ e. T! b% _8 X7 H5 o终于到了最后了~短的串的next值我们可以“看”出来，但长的串就需要借助程序了，具体算法刚接触的时候确实不容易理解，但给我的体验，把上面的内容写完，现在感觉简简单单了…先附上程序再做解释，(终于到了传说中的整整5行代码让我整理了一下午)。

% m0 p  U2 v2 S' z5 g$ \
int GetNext(char ch[],int cLen,int next[]){//cLen为串ch的长度
    next[1] = 0;
7 E' t0 s" u7 T) d: a7 E7 A( f    int i = 1,j = 0;
    while(i<=cLen){
: U$ ]" M; w* b3 G        if(j==0||ch==ch[j]) next[++i] = ++j;
        else j = next[j];
    }
}
' A& j4 y& C/ j3 A: Q9 a) E
还是先由一般再推优化：
直接求next[j+1]（至于为什么是j+1，是为了和下面的对应）
. @! d3 n6 ]0 o1 Y# V+ I) w根据之前的分析，next[j+1]的值为pj+1的前j个元素的收尾重合的最大个数加一。即需要满足两个条件，把它的值一步步“检验”出来。一是“个数最多”的，因此要从可能的最大值开始验；二是“首尾重合”，因此要一一对应验是否相等。
不难理解，next[j+1]的最大值为j，所有我们从next[j+1]=j开始“验证”。有以下优先判断顺序：
  n5 P$ g% Z* n5 Nif(P1…Pj-1 == P2…Pj) => next[j+1]=j
0 @3 P) d* `" W% N! aelse if(P1…Pj-2 == P3…Pj) =>next[j+1]=j-1
2 z! r; H- q- V4 u. @else if(P1…Pj-3 == P4…Pj) =>next[j+1]=j-2
" m; ?7 K/ B4 ]…
/ f& K% T# y, t; [2 X7 w: O…
…
3 L/ W' }: E# l- u0 Xelse 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
; t/ C" I7 m9 s( ~2 i% v每次前去尾1个，后掐头1个，直至得到next[j+1]

( _; M5 U$ O" y3 l) `
再进一步想，next值是一个“工具”，我们单独的求next[j+1]是完全没有意义的，就是说要求next就要把所有j的next求出来。所有一般的，我们都是已知前j个元素的next值，求next[j+1]，以此递推下去，求完整的next数组。
! Q. p$ O8 t  W$ ~5 |' X% u  C但是，上面的思考过程还是最根本的。所以问题变为两个：知道前j个元素的next的情况下，
% i$ q" y1 C. L' a" [, Y$ g- r①next[j+1]的可能的最大值是多少（即从哪开始验证）
3 y9 e& Q4 v8 E4 h1 P% T/ U. E②某一步验证失败后，需要“前去尾几个，后掐头几个？”（即本次验证失败后，再验证哪个值）
& v! q! r' k; a7 w' N看一下的分析：
# E$ U" F. Q% \" Y

1、next[j+1]的最大值为next[j]+1。
3 W  |, g/ ?, m/ C/ y! x. D因为：
假设next[j]=k1，则可以说明P1…Pk1-1=Pj-k1+1…Pj-1，且这是前j个元素最大的首尾重合序列。
2 q6 T  X9 ^+ p. g" J) M& v5 U如果Pk1=Pj，那么P1…Pk1-1PK=Pj-k1+1…Pj-1Pj，那么k+1这也是前j+1个元素的最大首尾重合序列，也即next[j+1]的值为k1+1
: q6 L# W; k8 ~0 L# i2、如果Pk1≠Pj，那么next[j+1]可能的次大值为next[next[j]]+1，以此类推即可高效求出next[j+1]
/ }/ g/ L+ s! g' I* Y/ t这里不好解释，直接看下面的流程分析及图解


7 y: t: C: R: w开——始——划——重——点！
从头走一遍流程
8 Z% s/ p4 J, u# L2 N①求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，否则
/ b0 m+ d( v$ D④已知next[k1]=k2，则有P1…Pk2-1 = Pk1-k2+1…Pk1-1
" S  N) ]+ J& I8 p. `( t, |& J⑤第二第三步联合得到:
5 ^' @8 n/ n6 o: q/ ]P1…Pk2-1 = Pk1-k2+1…Pk1-1 = Pj-k1+1…Pk2-k1+j-1 = Pj-k2+1…Pj-1 即四段重合
3 A1 I( A) a6 K2 T4 q⑥这时候，再判断如果Pk2=Pj，则P1…Pk2-1P~k2 = Pj-k2+1…Pj-1Pj，则next[j+1]=k2+1；否则再取next[k2]=k3…以此类推
8 E! ?4 F. P6 N
$ N0 T* Q) H7 S3 v7 `, p
' U4 i* I/ J' R/ g% B6 D. q' ]& R# n) I上面几步，耐心看下来，结合那个式子很容易看懂。最后，再加一个图的模拟帮助理解：
; x% D. A. U( M7 H1 l% q$ o1 J1、要求next[k+1] 其中k+1=17
" C7 I3 S  z, C9 V) `
! E4 S. v# {6 ^0 s  O6 K
2、已知next[16]=8，则元素有以下关系：
8 Q6 ^9 N5 _. ?3 [4 t

3、如果P8=P16，则明显next[17]=8+1=9
4、如果不相等，又若next[8]=4，则有以下关系
! Z9 {" d! }; O4 s' S, _
: j: ]2 h* X/ b/ f" c* I" e
又加上2的条件知

: ?# f: K. n/ t4 {! U: \8 H
主要是为了证明：
% }, Y/ \  z6 J5 @
+ O. ]( M; _% H; r. E' [  ]: y# h
5、现在在判断，如果P16=P4则next[17]=4+1=5，否则，在继续递推
6、若next[4]=2，则有以下关系

# W2 |/ x# P( ~
7、若P16=P2，则next[17]=2+1=3;否则继续取next[2]=1、next[1]=0；遇到0时还没出结果，则递推结束，此时next[17]=1。最后，再返回看那5行算法，应该很容易明白了！
# E1 A% j7 v; F+ W' s& Q: V5 A————————————————
- W5 G, K" f/ J4 {# U版权声明：本文为CSDN博主「Sirm23333」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_37969433/article/details/82947411

4 r5 j9 s2 g: ^+ |' J- m
% ^, U% a% d! ]' J2 D' u1 C% s