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

杨利霞

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

4 n3 t1 E0 x: a' V8 g. e大多数据结构课本中，串涉及的内容即串的模式匹配，需要掌握的是朴素算法、KMP算法及next值的求法。在考研备考中，参考严奶奶的教材，我也是在关于求next值的算法中卡了一下午时间，感觉挺有意思的，把一些思考的结果整理出来，与大家一起探讨。
3 l# e8 v( u; [0 Y4 G* ~! D8 @

本文的逻辑顺序为
+ o# c4 C+ O2 n5 z6 u9 b4 j7 H3 q1、最基本的朴素算法
, D$ |5 O, H1 Y! s2、优化的KMP算法
3、应算法需要定义的next值
4、手动写出较短串的next值的方法
5、最难理解的、足足有5行的代码的求next值的算法
- }( z+ E5 g, }0 Z所有铺垫为了最后的第5点，我觉得以这个逻辑下来，由果索因还是相对好理解的，下面写的很通俗，略显不专业…
0 q( h; B# {' v& r
7 G% B/ Q: z% j$ Y7 H% w- r2 V
一、问题描述
* _5 B) w; ]2 v5 A2 F$ K给定一个主串S及一个模式串P，判断模式串是否为主串的子串；若是，返回匹配的第一个元素的位置（序号从1开始），否则返回0；如S=“abcd”，P=“bcd”，则返回2；S=“abcd”，P=“acb”，返回0。

5 O- e+ R5 `, F' O. K; f' a
二、朴素算法
最简单的方法及一次遍历S与P。以S=“abcabaaaabaaacac”,P="abaabcac"为例，一张动图模拟朴素算法：


# k( H8 x4 J) v+ j  s
( l5 p7 d/ o) L5 K9 o# h! b
这个算法简单，不多说，附上代码


: }* `. z$ Z) C( j$ A( u* I#include<stdio.h>
int Index_1(char s[],int sLen,char p[],int pLen){//s为主串，sLen为主串元素个数，p为模式串，pLen为模式串的个数
& j- c" M8 n# y    if(sLen<pLen)return 0;
    int i = 1,j = 1;
% |" a6 I4 E9 O$ e' ?" j  [  T    while(i<=sLen && j<=pLen){
- P4 q5 l; F2 D1 i/ O% W) O1 j        if(s==p[j]){i++;j++;}
) J; \9 f0 f1 [0 |" h        else{
            i = i-j+2;
            j = 1;
2 \$ c9 b# F' l2 N% Y& ~5 L6 `+ J' Z        }
    }
    if(j>pLen) return i-pLen;
8 C  Z' w3 a) a! {5 K5 V) z    return 0;
}
void main(){
! e2 h3 r1 q# N0 q. H    char s[]={' ','a','b','c','a','b','a','a','a','a','b','a','a','b','c','a','c'};//从序号1开始存
8 ^6 ^$ X( _' K* I# X    char p[]={' ','a','b','a','a','b','c','a','c'};
1 L4 u, J+ V- I2 @# ]* V1 y- p- N    int sLen = sizeof(s)/sizeof(char)-1;
8 o8 t3 o0 w6 M" E; {    int pLen = sizeof(p)/sizeof(char)-1;
8 g) ~0 Q/ k' ~( W    printf("%d",Index_1(s,sLen,p,pLen));
}
1
2
3
% @0 c) f* }6 ^4
5 Q  K3 ~6 ^  d8 m. y! a: A& L5
( j; @3 D% h+ b. o3 A7 f6
7
5 D7 {2 r5 e+ @$ M; z" v$ H8
+ M$ Z. T9 }( P/ N. B9
6 c/ ~" C& X  n5 X& h/ v10
11
12
13
# ]. Q  d  d/ I14
15
) r  \1 s3 R, w' \( r3 E& ?! H16
% B$ x3 a+ g- j2 E' T3 X17
18
19
4 J' E4 }" t7 A" C20
21
三、改进的算法——KMP算法
- A, Q$ ~7 O) x. n' |5 o, e朴素算法理解简单，但两个串都有依次遍历，时间复杂度为O(n*m)，效率不高。由此有了KMP算法。
" h- v7 B) e- s+ q* @9 L4 B/ W: p! r0 m  ]一般的，在一次匹配中，我们是不知道主串的内容的，而模式串是我们自己定义的。
. j9 C% T2 U! V朴素算法中，P的第j位失配，默认的把P串后移一位。
" B$ E+ F; t% T但在前一轮的比较中，我们已经知道了P的前(j-1)位与S中间对应的某(j-1)个元素已经匹配成功了。这就意味着，在一轮的尝试匹配中，我们get到了主串的部分内容，我们能否利用这些内容，让P多移几位(我认为这就是KMP算法最根本的东西)，减少遍历的趟数呢？答案是肯定的。再看下面改进后的动图：



0 a6 l! c. E" n+ \5 @
4 F+ w$ A; V- l& [1 @" z: O这个模拟过程即KMP算法，若没有看明白，继续往下看相应的解释，理解需要把P多移几位，然后回头再看一遍这个图就很明了了。

/ ~. K! p4 |( |6 _* D- E0 H
相比朴素算法：
8 Z+ x& \. [1 Q9 ^' p, p" @朴素算法： 每次失配，S串的索引i定位的本次尝试匹配的第一个字符的后一个。P串的索引j定位到1；T(n)=O(n*m)
" {- s6 t) M, W& E/ x, DKMP算法： 每次失配，S串的索引i不动，P串的索引j定位到某个数。T(n)=O(n+m)，时间效率明显提高
1 h$ Z0 J( y/ R, @
2 Z) \8 ^8 @: j; f; f
4 Z& H' x2 J# g* s6 Y+ k而这“定位到某个数”，这个数就是接下来引入的next值。（实际上也就是P往后移多少位，换一种说法罢了：从上图中也可以看出，失配时固定i不变，令S与P[某个数]对齐，实际上是P右移几位的另一种表达，只有为什么这么表达，当然是因为程序好写。）
5 ?2 N7 {8 J( h4 s# \) \
/ L0 Q- K$ U4 T4 o
开——始——划——重——点！（图对逻辑关系比较好理解，但i和j的关系对后面求next的算法好理解！）

- w/ B, h, o8 t: h! k
; V* x' w: E* D* x) I+ r4 u比如，Pj处失配，绿色的是Pj，则我们可以确定P1…Pj-1是与Si…Si+j-2相对应的位置一一相等的
5 i; w! u: N% H  j
# R* _/ `, u+ B$ s
, U# `; [! c/ H4 v( o' A9 _
6 Z- [* l: h! d4 c5 U8 i2 I假设P1…Pj-1中，P1…Pk-1与Pj-k+1…Pj-1是一一相等的，为了下面说的清楚，我们把这种关系叫做“首尾重合”


$ E1 Z* x# u) W- |- w1 ]& d9 T
: s% U( D, r6 p; l. V7 ^3 v6 N0 [
- t1 e" [; J; G" @* z+ m! c7 ~2 r那么可以推出，P1…Pk-1与Si…Si+j-2
+ d( ^0 v& G& @3 f2 S: N

% {- }& F) D4 h5 O6 U; Q. P

5 z% J& T4 W/ q显然，接下来要做的就是把模式串右移了，移到哪里就不用多说了：
* M4 y- v+ T6 v- a/ u  B+ T

( ?  h+ x$ e. f% W! \/ d* o

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

$ {1 M8 ?5 H, G) B' \4 @9 X
最后，如果我们知道了一个字符串的next值，那么KMP算法也就很好懂了。相比朴素算法，当发生失配时，i不变，j=next[j]就好啦！接下来就是怎么确定next值了。
6 |6 u, r7 k7 ]7 E$ L! y! g1 K

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


这个扫一眼就能依次写出，会了这个方法，应付个期末考试没问题了。


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


! k' X# g2 S: l) o: f! M

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


. O) s; @/ k3 v" a4 cint GetNext(char ch[],int cLen,int next[]){//cLen为串ch的长度
    next[1] = 0;
    int i = 1,j = 0;
5 Z2 s4 Y5 J$ ?  x2 O  ]2 ]/ U6 F    while(i<=cLen){
        if(j==0||ch==ch[j]) next[++i] = ++j;
# `& w' c5 H. u1 c( M        else j = next[j];
    }
}

( _4 l' u- V: o) Q* Q, p+ L8 Q/ z5 d还是先由一般再推优化：
0 c6 ?+ W7 }) o+ l5 W9 ~直接求next[j+1]（至于为什么是j+1，是为了和下面的对应）
根据之前的分析，next[j+1]的值为pj+1的前j个元素的收尾重合的最大个数加一。即需要满足两个条件，把它的值一步步“检验”出来。一是“个数最多”的，因此要从可能的最大值开始验；二是“首尾重合”，因此要一一对应验是否相等。
" w  y) ~5 d" A( r  [不难理解，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
else if(P1…Pj-3 == P4…Pj) =>next[j+1]=j-2
…
…
7 X" ^6 j0 C& C. l& G9 F…
else if(P1P2 == Pj-1Pj) => next[j+1]=3
7 S5 `( {% z% m9 p* R2 ~else if(P1 == Pj-1) => next[j+1]=2
2 |( b: A! S+ X( J1 delse if(P1 != Pj-1) => next[j+1]=1
! l. b1 i' J& b2 R, R9 l4 B每次前去尾1个，后掐头1个，直至得到next[j+1]
  p, _" ~# s* q2 w% H& {9 |

再进一步想，next值是一个“工具”，我们单独的求next[j+1]是完全没有意义的，就是说要求next就要把所有j的next求出来。所有一般的，我们都是已知前j个元素的next值，求next[j+1]，以此递推下去，求完整的next数组。
' J: e! S/ |4 G( p1 ~* b, [2 x6 C但是，上面的思考过程还是最根本的。所以问题变为两个：知道前j个元素的next的情况下，
①next[j+1]的可能的最大值是多少（即从哪开始验证）
②某一步验证失败后，需要“前去尾几个，后掐头几个？”（即本次验证失败后，再验证哪个值）
看一下的分析：
' h3 }) i& ~  V% a! [* G: h7 J% `

1、next[j+1]的最大值为next[j]+1。
3 B' n$ u* d" O: b% ^因为：
, o4 }' o0 K$ F" _- t" L假设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
+ h/ k: }0 h8 o8 l/ j- |# b) m2、如果Pk1≠Pj，那么next[j+1]可能的次大值为next[next[j]]+1，以此类推即可高效求出next[j+1]
* N  F" {" M6 N这里不好解释，直接看下面的流程分析及图解
; s6 w1 l+ s2 f6 K# W8 \! d

  k) w1 \- K; ^  O% u6 l开——始——划——重——点！
从头走一遍流程
①求next[j+1]，设值为m
( [# Y* ^, F8 i$ P- ~# 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
: n3 W) H1 q2 H: Y: ~- r, [' G' ?⑤第二第三步联合得到:
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…以此类推
  @6 J& T0 K4 R6 m

' s. c6 j! W9 A% d# U6 n1 ^: z2 Y上面几步，耐心看下来，结合那个式子很容易看懂。最后，再加一个图的模拟帮助理解：
1 p' R' b% Q0 ~8 j1、要求next[k+1] 其中k+1=17

2 Z$ f6 Q) e* C9 {$ _/ k0 P
9 D  D' G$ D! E4 l+ X- p: U0 y2、已知next[16]=8，则元素有以下关系：
: N; u+ t( q5 x- ]- Y8 t( d

7 K! S  S* v- N: e" ~  I3、如果P8=P16，则明显next[17]=8+1=9
4、如果不相等，又若next[8]=4，则有以下关系
) `% U- M; g8 r9 J. E* G
* S* z$ S5 @  l+ @8 M9 F4 q
又加上2的条件知

3 S" c- \4 }  j1 a/ p
主要是为了证明：

. Z6 v* q* P2 Y2 H: m# }
5、现在在判断，如果P16=P4则next[17]=4+1=5，否则，在继续递推
: ~0 x$ F) {7 t3 W# `6、若next[4]=2，则有以下关系


6 d6 T- a  Z1 v8 _  e7、若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

8 y8 M7 t4 n% g- Z( C7 }* z