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

杨利霞

（算法）通俗易懂的字符串匹配KMP算法及求next值算法
3 V+ w, u. \, Y# |
大多数据结构课本中，串涉及的内容即串的模式匹配，需要掌握的是朴素算法、KMP算法及next值的求法。在考研备考中，参考严奶奶的教材，我也是在关于求next值的算法中卡了一下午时间，感觉挺有意思的，把一些思考的结果整理出来，与大家一起探讨。
# v& _6 i0 w3 X) i' y% D' @
# ?* h- C# J; j% E8 X
本文的逻辑顺序为
1、最基本的朴素算法
# I6 J2 H' E3 b( W2、优化的KMP算法
3、应算法需要定义的next值
9 Z+ g  v" ~  `; N# ?1 v4、手动写出较短串的next值的方法
4 \" E' U) }+ v3 V+ n5、最难理解的、足足有5行的代码的求next值的算法
0 q5 ^+ m3 Z. v3 b所有铺垫为了最后的第5点，我觉得以这个逻辑下来，由果索因还是相对好理解的，下面写的很通俗，略显不专业…
; @) r3 Y) M' ?3 N6 G/ L

一、问题描述
给定一个主串S及一个模式串P，判断模式串是否为主串的子串；若是，返回匹配的第一个元素的位置（序号从1开始），否则返回0；如S=“abcd”，P=“bcd”，则返回2；S=“abcd”，P=“acb”，返回0。
, @' o8 S) V! j  g9 ]% K) H

二、朴素算法
最简单的方法及一次遍历S与P。以S=“abcabaaaabaaacac”,P="abaabcac"为例，一张动图模拟朴素算法：
, O0 ]# P- z3 B0 @) K



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


  i6 B+ X7 w; m% o5 C# A+ I( U#include<stdio.h>
0 t' w- Y( ^0 E$ w) gint 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++;}
. k- o9 J' i8 Y2 N1 ~        else{
4 ~9 t( D6 e. f1 W6 F4 a0 c; t            i = i-j+2;
            j = 1;
& p. b( W% c! u1 G$ Z6 d% ^        }
    }
( F& ~2 f+ P. ]  m5 l3 ^6 k    if(j>pLen) return i-pLen;
' _8 ?$ a. r/ _- c0 N+ ]( K8 w1 I    return 0;
}
2 E! @3 d! c6 J4 H9 }& h# I, bvoid main(){
& S0 Y/ j- M" Z3 v) \6 N- \) k    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;
& L4 @+ A- Q# q* n# L! \    printf("%d",Index_1(s,sLen,p,pLen));
}
1
( v% `* p- e0 S' N- F2
3
4
; O- g" E/ p+ i* e( n( k* R5
6
& p$ U# J" q% q) {$ u7
8
9 a. @$ p* p! x9
' L( `; e" M% A5 l& ?# l10
11
12
9 R. F/ O$ K8 w8 l# ?% Y13
  F0 p' U6 W/ E  _' _14
15
( ?1 d0 H& ^& N7 |/ b16
1 z" j% u; p4 a17
18
19
20
1 H! \1 k" h7 B; s" d2 ~+ Z5 q4 Q21
" b0 {; ^& I+ k0 p- K7 [- w# f三、改进的算法——KMP算法
! `6 k3 n1 c3 O! U9 b7 L; f朴素算法理解简单，但两个串都有依次遍历，时间复杂度为O(n*m)，效率不高。由此有了KMP算法。
一般的，在一次匹配中，我们是不知道主串的内容的，而模式串是我们自己定义的。
6 g( l2 v6 j" S) {! {朴素算法中，P的第j位失配，默认的把P串后移一位。
2 d0 N) ^% m" Z; H- N但在前一轮的比较中，我们已经知道了P的前(j-1)位与S中间对应的某(j-1)个元素已经匹配成功了。这就意味着，在一轮的尝试匹配中，我们get到了主串的部分内容，我们能否利用这些内容，让P多移几位(我认为这就是KMP算法最根本的东西)，减少遍历的趟数呢？答案是肯定的。再看下面改进后的动图：

; R8 f0 {3 b6 U- f
% q- W& s7 x' N; N

- W' J/ j$ W4 U3 f' d这个模拟过程即KMP算法，若没有看明白，继续往下看相应的解释，理解需要把P多移几位，然后回头再看一遍这个图就很明了了。
1 m( f5 d7 l: m/ v; C
+ Y  h1 v, ~0 z6 S+ }
( g; o* q0 W) W' q8 `$ O+ B相比朴素算法：
朴素算法： 每次失配，S串的索引i定位的本次尝试匹配的第一个字符的后一个。P串的索引j定位到1；T(n)=O(n*m)
" p% Y, S2 Z; n3 A" eKMP算法： 每次失配，S串的索引i不动，P串的索引j定位到某个数。T(n)=O(n+m)，时间效率明显提高
9 ?  F  d' F0 s' l3 W
  ?' S2 O( b3 g* c& \  r. d
而这“定位到某个数”，这个数就是接下来引入的next值。（实际上也就是P往后移多少位，换一种说法罢了：从上图中也可以看出，失配时固定i不变，令S与P[某个数]对齐，实际上是P右移几位的另一种表达，只有为什么这么表达，当然是因为程序好写。）
8 _# o( [+ Y) d; j% P/ n$ B8 z
  y7 a& X7 g* K4 `
3 [# M4 J- ^$ G( c# G  L5 C开——始——划——重——点！（图对逻辑关系比较好理解，但i和j的关系对后面求next的算法好理解！）
9 X% f0 s4 \3 e

* w& F; C2 H4 M2 _( t比如，Pj处失配，绿色的是Pj，则我们可以确定P1…Pj-1是与Si…Si+j-2相对应的位置一一相等的
0 Q) s6 d% h3 \) U6 L* e  l$ ~
  {* ]; j, _, D

假设P1…Pj-1中，P1…Pk-1与Pj-k+1…Pj-1是一一相等的，为了下面说的清楚，我们把这种关系叫做“首尾重合”


6 |2 Q' {/ v" Z& L, n3 m, v7 |! B
3 L; x% f" L  C2 N5 x5 U
那么可以推出，P1…Pk-1与Si…Si+j-2
! l3 I4 j. @2 T) |/ g! t# V, L: ?
. H3 |" a+ A5 W+ U


6 R) D  J; w8 R4 g$ s显然，接下来要做的就是把模式串右移了，移到哪里就不用多说了：

- X# }8 r% ]# D4 L
. w  Q6 X7 d# \; v/ |) t* ~2 s6 ]8 r; R

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


9 o9 f. Z% m- L' M最后，如果我们知道了一个字符串的next值，那么KMP算法也就很好懂了。相比朴素算法，当发生失配时，i不变，j=next[j]就好啦！接下来就是怎么确定next值了。
) ]* A' r* D. |6 f+ w1 O1 r
: y$ g* G/ |8 d" x) h7 p' k. G: B7 x# b
四、手动写出一个串的next值
# D! h* D; w& b, {我们规定任何一个串，next[1]=0。(不用next[0]，与串的所有对应)，仍是一张动图搞定问题：


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

- _. A' L1 \# N- q+ D) V* n8 \$ G
% T5 b  p9 Q+ N通过把next值“看”出来，我们再来分析next值，这就很容易得到超级有名的公式了，这个式子对后面的算法理解很重要！所以先要看懂这个式子，如果上面的内容通下来了，这个应该很容易看懂了：


+ r, w% n+ B/ i* ]( m

五、求next的算法
终于到了最后了~短的串的next值我们可以“看”出来，但长的串就需要借助程序了，具体算法刚接触的时候确实不容易理解，但给我的体验，把上面的内容写完，现在感觉简简单单了…先附上程序再做解释，(终于到了传说中的整整5行代码让我整理了一下午)。
' r# C" e8 a1 [. ^( |& v$ c# U
: t1 e7 _- w0 k! u
int GetNext(char ch[],int cLen,int next[]){//cLen为串ch的长度
    next[1] = 0;
    int i = 1,j = 0;
    while(i<=cLen){
        if(j==0||ch==ch[j]) next[++i] = ++j;
+ `- L# Z7 E* I6 c2 u        else j = next[j];
    }
9 C0 b( q% p, G. ^" c}
1 t. W. i) O/ L* Y% V2 c/ Q* y
还是先由一般再推优化：
! y, R0 \  p! f6 E  R直接求next[j+1]（至于为什么是j+1，是为了和下面的对应）
根据之前的分析，next[j+1]的值为pj+1的前j个元素的收尾重合的最大个数加一。即需要满足两个条件，把它的值一步步“检验”出来。一是“个数最多”的，因此要从可能的最大值开始验；二是“首尾重合”，因此要一一对应验是否相等。
不难理解，next[j+1]的最大值为j，所有我们从next[j+1]=j开始“验证”。有以下优先判断顺序：
* p, o& ]* W% B; L  ^5 }if(P1…Pj-1 == P2…Pj) => next[j+1]=j
2 U& P5 x$ Q! T. [else if(P1…Pj-2 == P3…Pj) =>next[j+1]=j-1
9 d+ @/ p$ ~5 Gelse if(P1…Pj-3 == P4…Pj) =>next[j+1]=j-2
9 T9 D9 Z4 X( J" z. c8 t9 \…
…
…
$ h& I7 g* d+ k( T" pelse 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]
* W) p8 P5 {2 s7 S( Z! m

再进一步想，next值是一个“工具”，我们单独的求next[j+1]是完全没有意义的，就是说要求next就要把所有j的next求出来。所有一般的，我们都是已知前j个元素的next值，求next[j+1]，以此递推下去，求完整的next数组。
但是，上面的思考过程还是最根本的。所以问题变为两个：知道前j个元素的next的情况下，
5 f  P, ^0 I3 u, d1 ?; [7 Z7 _①next[j+1]的可能的最大值是多少（即从哪开始验证）
- Y9 v, N% F  Y$ i! N: `②某一步验证失败后，需要“前去尾几个，后掐头几个？”（即本次验证失败后，再验证哪个值）
1 z/ g, w' A& w, R5 k- F9 K% k看一下的分析：

/ ?' U3 [# x6 e7 k5 b
1、next[j+1]的最大值为next[j]+1。
因为：
# k' W8 B$ [$ @  h( h假设next[j]=k1，则可以说明P1…Pk1-1=Pj-k1+1…Pj-1，且这是前j个元素最大的首尾重合序列。
8 y. Z/ N. j: M7 \$ r' q' p如果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]
3 h* r; s" W  c; x这里不好解释，直接看下面的流程分析及图解
- \4 m6 @, C+ \5 c

开——始——划——重——点！
$ o$ Z; ^: J% P6 L5 Q, L从头走一遍流程
; K9 W# Y* ^1 M. G. C! ?①求next[j+1]，设值为m
7 l- F: d- d0 t②已知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
# P3 R) w* T; Q; q2 t⑤第二第三步联合得到:
P1…Pk2-1 = Pk1-k2+1…Pk1-1 = Pj-k1+1…Pk2-k1+j-1 = Pj-k2+1…Pj-1 即四段重合
0 X  A* n4 a7 I  B⑥这时候，再判断如果Pk2=Pj，则P1…Pk2-1P~k2 = Pj-k2+1…Pj-1Pj，则next[j+1]=k2+1；否则再取next[k2]=k3…以此类推


9 P% h. c( ]) V+ h7 |上面几步，耐心看下来，结合那个式子很容易看懂。最后，再加一个图的模拟帮助理解：
; ]; Z' p% e- U2 k1、要求next[k+1] 其中k+1=17
' [6 E) t6 B+ D. x4 N
7 ]3 h! C4 @3 d$ x7 |: ~
2、已知next[16]=8，则元素有以下关系：

. z, W( O4 L' \4 y+ P( ?4 n9 G
3、如果P8=P16，则明显next[17]=8+1=9
' h# H4 L6 T! \4、如果不相等，又若next[8]=4，则有以下关系
# b% J+ a5 b- P6 [

又加上2的条件知
  k1 D5 u' G8 G% `. Y

主要是为了证明：


5、现在在判断，如果P16=P4则next[17]=4+1=5，否则，在继续递推
" Z  D+ g! Q+ `1 `& u6、若next[4]=2，则有以下关系
! S7 ?, T; n- o7 k9 O4 N+ T
* N+ I0 ^3 j2 O6 g3 Q
# D9 d7 C- Y1 E0 o7、若P16=P2，则next[17]=2+1=3;否则继续取next[2]=1、next[1]=0；遇到0时还没出结果，则递推结束，此时next[17]=1。最后，再返回看那5行算法，应该很容易明白了！
! m; \* \/ U% d( w————————————————
版权声明：本文为CSDN博主「Sirm23333」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_37969433/article/details/82947411
- {' w' W1 V; ?1 a$ q% {, J
  h. d0 N+ J9 v% v