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

杨利霞

（算法）通俗易懂的字符串匹配KMP算法及求next值算法
+ R9 b' ^) F. u6 @: w
大多数据结构课本中，串涉及的内容即串的模式匹配，需要掌握的是朴素算法、KMP算法及next值的求法。在考研备考中，参考严奶奶的教材，我也是在关于求next值的算法中卡了一下午时间，感觉挺有意思的，把一些思考的结果整理出来，与大家一起探讨。


本文的逻辑顺序为
/ W: r* i1 g* l$ A' F7 P' m! y1、最基本的朴素算法
2、优化的KMP算法
, c3 w  X( O& {& x5 N  [: M2 b& g$ t& E3、应算法需要定义的next值
4、手动写出较短串的next值的方法
* l( ^" a9 q5 T- |* D8 I& h, u5、最难理解的、足足有5行的代码的求next值的算法
5 h; o. ~- b5 y+ H1 D' e所有铺垫为了最后的第5点，我觉得以这个逻辑下来，由果索因还是相对好理解的，下面写的很通俗，略显不专业…
4 j0 e4 @5 p# D( M  J0 j
$ t, B8 z" @4 C% y* {# M
一、问题描述
给定一个主串S及一个模式串P，判断模式串是否为主串的子串；若是，返回匹配的第一个元素的位置（序号从1开始），否则返回0；如S=“abcd”，P=“bcd”，则返回2；S=“abcd”，P=“acb”，返回0。


二、朴素算法
) R" {5 `: N; }3 z$ Q1 u0 g最简单的方法及一次遍历S与P。以S=“abcabaaaabaaacac”,P="abaabcac"为例，一张动图模拟朴素算法：
  f: e/ C* y8 f2 O* V5 @: ]9 G
. O' O& P% S& C6 \8 t: ^5 J
. b5 ?9 C, j- ^& f# d% x

这个算法简单，不多说，附上代码
$ |8 u$ |- N$ r

#include<stdio.h>
int Index_1(char s[],int sLen,char p[],int pLen){//s为主串，sLen为主串元素个数，p为模式串，pLen为模式串的个数
( Q  L  Q2 E) @  r+ _* W    if(sLen<pLen)return 0;
    int i = 1,j = 1;
' O* K% m! w& j$ [4 n* [  c    while(i<=sLen && j<=pLen){
        if(s==p[j]){i++;j++;}
        else{
7 d& l: _) m4 L* J            i = i-j+2;
  e* N  ]/ n! ~6 i2 @1 U" Y            j = 1;
3 z5 g& O) c& T# z+ O        }
2 X, B( g! U/ s1 w2 m6 x( p    }
    if(j>pLen) return i-pLen;
) `' I9 f- n5 @    return 0;
5 D2 O9 ]. e7 d+ u' O- c8 F6 L}
void main(){
% U" u5 ~6 m9 E! ~2 Y8 i    char s[]={' ','a','b','c','a','b','a','a','a','a','b','a','a','b','c','a','c'};//从序号1开始存
7 ?7 c! N. Q* l; I) M    char p[]={' ','a','b','a','a','b','c','a','c'};
    int sLen = sizeof(s)/sizeof(char)-1;
    int pLen = sizeof(p)/sizeof(char)-1;
8 N1 C) N- V& }8 t% L8 ^    printf("%d",Index_1(s,sLen,p,pLen));
4 Q* r$ [& a3 L5 a- D}
5 v/ F/ u, C0 A2 I1 R& u1
# L: t6 r$ d9 H  ^9 x7 q: j2
3
% V$ d* z( M  Z! s$ H4
' \' U9 m9 ?2 x* i4 {5
6
7
5 h3 L5 ?  T5 d% E8 u7 U8
9
10
11
12
6 R. V* p" k; ]7 S0 U$ h- @3 |13
6 H6 n% |" L3 D! F9 P6 c( t14
- e' x$ X- E; B9 V15
16
' h( L) `( G) D5 E2 ]0 n' @0 N& ^6 g( q17
6 N* f. P3 O6 J# |, P18
19
! F: p7 q$ \3 S5 T& D/ ]* R20
) ^% k0 ]& d9 ]/ o0 G( f% [21
$ @# C7 r& n2 a$ {* c4 m4 K三、改进的算法——KMP算法
0 ^* d/ S$ G7 [' _" F: l朴素算法理解简单，但两个串都有依次遍历，时间复杂度为O(n*m)，效率不高。由此有了KMP算法。
一般的，在一次匹配中，我们是不知道主串的内容的，而模式串是我们自己定义的。
朴素算法中，P的第j位失配，默认的把P串后移一位。
# S0 ?% `8 o( |7 u0 K6 T% d5 z但在前一轮的比较中，我们已经知道了P的前(j-1)位与S中间对应的某(j-1)个元素已经匹配成功了。这就意味着，在一轮的尝试匹配中，我们get到了主串的部分内容，我们能否利用这些内容，让P多移几位(我认为这就是KMP算法最根本的东西)，减少遍历的趟数呢？答案是肯定的。再看下面改进后的动图：
$ l7 R3 ~7 t) j) T- T* p1 _



/ V5 D+ A* X! o" b这个模拟过程即KMP算法，若没有看明白，继续往下看相应的解释，理解需要把P多移几位，然后回头再看一遍这个图就很明了了。
; Z4 a" O/ p; c$ Y* N$ }  G* c

相比朴素算法：
朴素算法： 每次失配，S串的索引i定位的本次尝试匹配的第一个字符的后一个。P串的索引j定位到1；T(n)=O(n*m)
) O5 A, {, N, V1 @* Q  r5 yKMP算法： 每次失配，S串的索引i不动，P串的索引j定位到某个数。T(n)=O(n+m)，时间效率明显提高
3 H- T* ~+ s; J2 ~/ |" |9 V- B5 ^; I
4 e) Q7 P) @' V6 u
& y9 a3 L% E7 ]+ j而这“定位到某个数”，这个数就是接下来引入的next值。（实际上也就是P往后移多少位，换一种说法罢了：从上图中也可以看出，失配时固定i不变，令S与P[某个数]对齐，实际上是P右移几位的另一种表达，只有为什么这么表达，当然是因为程序好写。）
7 b6 B+ Y) J0 U' N  V( l

- f3 a# X9 T- P8 R开——始——划——重——点！（图对逻辑关系比较好理解，但i和j的关系对后面求next的算法好理解！）


比如，Pj处失配，绿色的是Pj，则我们可以确定P1…Pj-1是与Si…Si+j-2相对应的位置一一相等的
+ \; s3 B5 [! x3 f
) m" a: B1 J: g! b2 i2 E
! ?8 f2 c: P; L4 U" Q2 B" S& C
假设P1…Pj-1中，P1…Pk-1与Pj-k+1…Pj-1是一一相等的，为了下面说的清楚，我们把这种关系叫做“首尾重合”
+ m$ K: k, Z& K, T2 r$ b

' h$ O1 b5 @- O# E; b4 Z: r

2 s' k, U  k" H% q  f' w那么可以推出，P1…Pk-1与Si…Si+j-2
& u# v3 k1 }# A1 d) l; x
9 e8 K' H- |; o

' i; m+ A6 s' v% D3 H8 x
显然，接下来要做的就是把模式串右移了，移到哪里就不用多说了：

- r6 v3 |/ }5 m) E. t
8 Y& o. t7 p" T8 [7 _

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

/ u( ?! A! b1 e. n9 a  `9 K
最后，如果我们知道了一个字符串的next值，那么KMP算法也就很好懂了。相比朴素算法，当发生失配时，i不变，j=next[j]就好啦！接下来就是怎么确定next值了。
" K# y6 }6 w: I) s1 }! u

四、手动写出一个串的next值
" z+ y3 E% v5 J* M( B0 O% |我们规定任何一个串，next[1]=0。(不用next[0]，与串的所有对应)，仍是一张动图搞定问题：
' H3 X8 B, W6 d" m9 C! u4 ^6 h# K
. }0 d3 R) a( F- O" e* q  I8 B$ E
' p+ A% a1 Q+ E( B. c; D5 S) ~; E这个扫一眼就能依次写出，会了这个方法，应付个期末考试没问题了。
' i0 `1 f) A2 V' d" K
+ Q! `: B3 i3 W
通过把next值“看”出来，我们再来分析next值，这就很容易得到超级有名的公式了，这个式子对后面的算法理解很重要！所以先要看懂这个式子，如果上面的内容通下来了，这个应该很容易看懂了：



2 i3 }- F5 K& S6 D0 i; x5 v
五、求next的算法
终于到了最后了~短的串的next值我们可以“看”出来，但长的串就需要借助程序了，具体算法刚接触的时候确实不容易理解，但给我的体验，把上面的内容写完，现在感觉简简单单了…先附上程序再做解释，(终于到了传说中的整整5行代码让我整理了一下午)。

7 g$ I; m4 B# |
, c7 c" O+ D. z. s' Kint GetNext(char ch[],int cLen,int next[]){//cLen为串ch的长度
5 b# L4 @6 B2 k3 y4 t2 c    next[1] = 0;
4 r9 ?# g  T7 z+ v% r& T/ I    int i = 1,j = 0;
% ^! ?! e9 z# V0 |# u3 t+ e4 Y    while(i<=cLen){
        if(j==0||ch==ch[j]) next[++i] = ++j;
% S) v5 W" M: _. h  P        else j = next[j];
' j# j- \" l( |9 ^2 ~0 E& r    }
}

还是先由一般再推优化：
直接求next[j+1]（至于为什么是j+1，是为了和下面的对应）
根据之前的分析，next[j+1]的值为pj+1的前j个元素的收尾重合的最大个数加一。即需要满足两个条件，把它的值一步步“检验”出来。一是“个数最多”的，因此要从可能的最大值开始验；二是“首尾重合”，因此要一一对应验是否相等。
& F+ a; B4 S" O, ]. ?不难理解，next[j+1]的最大值为j，所有我们从next[j+1]=j开始“验证”。有以下优先判断顺序：
; C4 L" b( J# P5 Tif(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
…
…
…
else if(P1P2 == Pj-1Pj) => next[j+1]=3
) h% K$ B* i( D+ v; I+ Gelse if(P1 == Pj-1) => next[j+1]=2
else if(P1 != Pj-1) => next[j+1]=1
每次前去尾1个，后掐头1个，直至得到next[j+1]
, `, W6 @: A) N; r. {8 [; t  [
7 M$ ]2 _3 O  w5 O
& M# m9 m7 P/ ^' K9 h& b& D再进一步想，next值是一个“工具”，我们单独的求next[j+1]是完全没有意义的，就是说要求next就要把所有j的next求出来。所有一般的，我们都是已知前j个元素的next值，求next[j+1]，以此递推下去，求完整的next数组。
但是，上面的思考过程还是最根本的。所以问题变为两个：知道前j个元素的next的情况下，
①next[j+1]的可能的最大值是多少（即从哪开始验证）
②某一步验证失败后，需要“前去尾几个，后掐头几个？”（即本次验证失败后，再验证哪个值）
看一下的分析：


1、next[j+1]的最大值为next[j]+1。
因为：
1 Q* Z0 S$ e" b4 M  ^假设next[j]=k1，则可以说明P1…Pk1-1=Pj-k1+1…Pj-1，且这是前j个元素最大的首尾重合序列。
! Z" |6 U- m3 A( E1 a) j; |5 l' L9 [/ \如果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]
这里不好解释，直接看下面的流程分析及图解

2 E1 C% q) I, b( K* ?6 ^
; A8 q2 ^/ m% j9 Y& S8 [5 }开——始——划——重——点！
- P$ g9 M8 v3 r  i' _从头走一遍流程
①求next[j+1]，设值为m
9 O/ d6 s2 u% t& u) x②已知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
5 I% {6 P- J7 k& P# O⑤第二第三步联合得到:
P1…Pk2-1 = Pk1-k2+1…Pk1-1 = Pj-k1+1…Pk2-k1+j-1 = Pj-k2+1…Pj-1 即四段重合
; P  ], N3 A& x% F⑥这时候，再判断如果Pk2=Pj，则P1…Pk2-1P~k2 = Pj-k2+1…Pj-1Pj，则next[j+1]=k2+1；否则再取next[k2]=k3…以此类推


上面几步，耐心看下来，结合那个式子很容易看懂。最后，再加一个图的模拟帮助理解：
; _7 ?) s, V1 {  M+ K! R1、要求next[k+1] 其中k+1=17
3 ~7 O/ N3 s( ?+ G7 j8 M1 A7 K
& M% x6 A0 w3 w. h
: d. x" v7 @: z; _1 N2、已知next[16]=8，则元素有以下关系：


3、如果P8=P16，则明显next[17]=8+1=9
( }8 M& _3 E0 q& J) D4、如果不相等，又若next[8]=4，则有以下关系


6 @' j! ^; Q: y7 o1 O- C# a& t# L0 _又加上2的条件知
  e, N/ V/ D. [% y2 b8 ^  g
" z* j' H) I& A' W
主要是为了证明：

6 S3 r% E+ ]  Q) L  T
& s7 \/ f+ J3 G2 F5、现在在判断，如果P16=P4则next[17]=4+1=5，否则，在继续递推
& A4 s1 [/ [3 A6、若next[4]=2，则有以下关系
* w: p. m7 ~# g8 Y4 t
0 ^8 i/ D+ h1 b* ?! f  c) @
7、若P16=P2，则next[17]=2+1=3;否则继续取next[2]=1、next[1]=0；遇到0时还没出结果，则递推结束，此时next[17]=1。最后，再返回看那5行算法，应该很容易明白了！
' f! C+ |" E1 g# q3 O————————————————
版权声明：本文为CSDN博主「Sirm23333」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_37969433/article/details/82947411
1 a# F% b6 g) E- B7 \' U