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

杨利霞

（算法）通俗易懂的字符串匹配KMP算法及求next值算法
4 I) x  F; K! z) d& `- M3 N  r
大多数据结构课本中，串涉及的内容即串的模式匹配，需要掌握的是朴素算法、KMP算法及next值的求法。在考研备考中，参考严奶奶的教材，我也是在关于求next值的算法中卡了一下午时间，感觉挺有意思的，把一些思考的结果整理出来，与大家一起探讨。


% V6 V4 P/ g/ L: Q, X* e& y* {本文的逻辑顺序为
' O  \  D0 P7 K6 o* I1、最基本的朴素算法
. b% X7 X2 ?4 w8 }9 N5 F2、优化的KMP算法
3、应算法需要定义的next值
4、手动写出较短串的next值的方法
5、最难理解的、足足有5行的代码的求next值的算法
所有铺垫为了最后的第5点，我觉得以这个逻辑下来，由果索因还是相对好理解的，下面写的很通俗，略显不专业…
; J7 s/ t0 K+ @) B* F* M: [

一、问题描述
2 {4 N; ~4 W+ `; V1 h3 t+ V给定一个主串S及一个模式串P，判断模式串是否为主串的子串；若是，返回匹配的第一个元素的位置（序号从1开始），否则返回0；如S=“abcd”，P=“bcd”，则返回2；S=“abcd”，P=“acb”，返回0。

) R: B/ i5 h% m, j$ l! t1 K2 a
  }7 G' {8 j$ H: s二、朴素算法
5 C1 Q: R# x" w$ l& W8 J7 t最简单的方法及一次遍历S与P。以S=“abcabaaaabaaacac”,P="abaabcac"为例，一张动图模拟朴素算法：
5 X2 Q8 M% @. m0 w
. X- H$ Z9 _$ d9 V& p$ Y( G
5 y7 Y1 z, O5 n1 ~& S7 A* _
: D6 N+ y* m* K' F
5 g% t' {. e( T5 b4 P这个算法简单，不多说，附上代码
, i( @) P9 D& d' \
7 }3 B9 N+ {7 l  [
% P  R& {2 U- x/ f3 B0 K/ h#include<stdio.h>
int Index_1(char s[],int sLen,char p[],int pLen){//s为主串，sLen为主串元素个数，p为模式串，pLen为模式串的个数
9 X" P: m+ J4 h3 M4 s) v9 L    if(sLen<pLen)return 0;
8 I2 t3 @- Y7 I  E3 V$ F    int i = 1,j = 1;
    while(i<=sLen && j<=pLen){
' j" e% E" h9 |        if(s==p[j]){i++;j++;}
$ D3 U# ]: t+ U' y8 F        else{
            i = i-j+2;
+ f2 _; r1 w0 R+ O/ R3 a- d            j = 1;
        }
; F/ H% e+ i0 M) r% L/ N) _# `0 J    }
8 U  o; H6 n6 y    if(j>pLen) return i-pLen;
    return 0;
+ u% |! r: r, ~( l: Q}
void main(){
    char s[]={' ','a','b','c','a','b','a','a','a','a','b','a','a','b','c','a','c'};//从序号1开始存
/ E$ r# O6 v7 [  H5 i) x9 b5 w    char p[]={' ','a','b','a','a','b','c','a','c'};
    int sLen = sizeof(s)/sizeof(char)-1;
    int pLen = sizeof(p)/sizeof(char)-1;
, E# u2 o' H1 ^  U8 `/ a7 u    printf("%d",Index_1(s,sLen,p,pLen));
}
1
2
1 i, a/ h4 `8 p9 y( w9 X3
4
5
6
4 J! L  S! R( O7 H  O7
" d  w: w7 k, D: A8
% L! }9 [2 A! Q- E9
10
  G  x3 l, F3 L: M9 H- P11
' ~2 h0 g7 s' C3 Z12
. ~4 g2 r8 P' C7 t13
5 P9 Q3 n& ?" I% d: b! F) f14
15
7 T  s9 `/ F  B# R. i( m% A16
8 W0 [) I  x" L17
7 J% `8 J6 Z' P  D18
% Z( M3 M5 B% v/ f% n! r19
- c  C$ A& a7 B8 W20
21
三、改进的算法——KMP算法
0 Q7 b" }4 t/ i) z! H朴素算法理解简单，但两个串都有依次遍历，时间复杂度为O(n*m)，效率不高。由此有了KMP算法。
0 p5 |) w3 q9 s" D9 e一般的，在一次匹配中，我们是不知道主串的内容的，而模式串是我们自己定义的。
, l4 ~, U" j3 Y. C朴素算法中，P的第j位失配，默认的把P串后移一位。
4 V( X+ t& u( G- g; d" r但在前一轮的比较中，我们已经知道了P的前(j-1)位与S中间对应的某(j-1)个元素已经匹配成功了。这就意味着，在一轮的尝试匹配中，我们get到了主串的部分内容，我们能否利用这些内容，让P多移几位(我认为这就是KMP算法最根本的东西)，减少遍历的趟数呢？答案是肯定的。再看下面改进后的动图：

( z# P8 v  c4 b( F: e
6 P; M6 Y5 e5 f6 ?

这个模拟过程即KMP算法，若没有看明白，继续往下看相应的解释，理解需要把P多移几位，然后回头再看一遍这个图就很明了了。
& ^. i6 C3 J+ |( O7 i% [* l6 [: S. D

% \. k! n8 k# L, i4 z. s- }相比朴素算法：
朴素算法： 每次失配，S串的索引i定位的本次尝试匹配的第一个字符的后一个。P串的索引j定位到1；T(n)=O(n*m)
- M$ I0 E+ I4 A8 _, a2 ^KMP算法： 每次失配，S串的索引i不动，P串的索引j定位到某个数。T(n)=O(n+m)，时间效率明显提高
, ^" X* n) Y3 E+ P! X8 C4 D
  I- Z/ y8 C# r) `4 [
而这“定位到某个数”，这个数就是接下来引入的next值。（实际上也就是P往后移多少位，换一种说法罢了：从上图中也可以看出，失配时固定i不变，令S与P[某个数]对齐，实际上是P右移几位的另一种表达，只有为什么这么表达，当然是因为程序好写。）
- r" |5 N. k3 k. A7 G

& u4 ^1 _5 m9 P# \* _开——始——划——重——点！（图对逻辑关系比较好理解，但i和j的关系对后面求next的算法好理解！）
, v, u0 K* O; l7 `

比如，Pj处失配，绿色的是Pj，则我们可以确定P1…Pj-1是与Si…Si+j-2相对应的位置一一相等的

% s' ]" T" S# c1 y! O2 @

' L1 `( b5 d1 l$ t" n假设P1…Pj-1中，P1…Pk-1与Pj-k+1…Pj-1是一一相等的，为了下面说的清楚，我们把这种关系叫做“首尾重合”
9 t. G1 y" X+ o1 ^5 U3 D

0 V7 ]: w% L4 }- k2 C
$ w* A4 H, |3 w2 b. ?
那么可以推出，P1…Pk-1与Si…Si+j-2




显然，接下来要做的就是把模式串右移了，移到哪里就不用多说了：
' B) x' C. n6 y( \9 S
" a  d/ x! F) u% [1 w# `- K


为了表示下一轮比较j定位的地方，我们将其定义为next[j]，next[j]就是第j个元素前j-1个元素首尾重合部分个数加一，当然，为了能遍历完整，首尾重合部分的元素个数应取到最多，即next[j]应取尽量大的值，原因挺好理解的，可以想个例子模拟一下，会完美跳过正确结果。在上图中就是绿色元素的next值为蓝色元素的序号。也即，对于字符串P，next[8]=4。如此，再看一下上面的动图是不是清楚了不少。
' F3 Q; U/ ?% }8 y/ o
2 l* T: O7 h: ^! \, C
最后，如果我们知道了一个字符串的next值，那么KMP算法也就很好懂了。相比朴素算法，当发生失配时，i不变，j=next[j]就好啦！接下来就是怎么确定next值了。
3 @  B0 ^% E/ ~0 k' ?$ Z" v
, {) r1 S$ _! X2 P
$ C6 G" l, R* Z. q6 r& ^( c四、手动写出一个串的next值
. d* E# U6 q* d# |我们规定任何一个串，next[1]=0。(不用next[0]，与串的所有对应)，仍是一张动图搞定问题：
. J( Z8 M+ i  N+ |! P( e
& P9 x$ U4 Z4 h$ K8 J" ]/ j
, M" V! @9 Z: `这个扫一眼就能依次写出，会了这个方法，应付个期末考试没问题了。
/ `% h" L' R8 F5 B8 N% T

通过把next值“看”出来，我们再来分析next值，这就很容易得到超级有名的公式了，这个式子对后面的算法理解很重要！所以先要看懂这个式子，如果上面的内容通下来了，这个应该很容易看懂了：
% s  y" z% P, U3 X$ [; h+ J2 l9 _) V3 w
$ Z! j- A7 j$ E5 u8 R


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

' U" c/ F+ S% E* Z
int GetNext(char ch[],int cLen,int next[]){//cLen为串ch的长度
4 Z) J$ b2 e$ C8 U) @  ]' m    next[1] = 0;
! H6 H0 D2 k: t7 R. x    int i = 1,j = 0;
& y1 P: f& c+ y9 d8 r    while(i<=cLen){
5 x" J# Q/ `- v        if(j==0||ch==ch[j]) next[++i] = ++j;
" X2 k9 S, m% u1 r$ u        else j = next[j];
; L3 x' C8 f" e( e+ I  T    }
# B: h& @: ?; W2 a2 ?+ t3 G}
2 M: V! U1 P! i& j6 \8 g& h& q
还是先由一般再推优化：
直接求next[j+1]（至于为什么是j+1，是为了和下面的对应）
根据之前的分析，next[j+1]的值为pj+1的前j个元素的收尾重合的最大个数加一。即需要满足两个条件，把它的值一步步“检验”出来。一是“个数最多”的，因此要从可能的最大值开始验；二是“首尾重合”，因此要一一对应验是否相等。
  Z4 S; k8 _( u不难理解，next[j+1]的最大值为j，所有我们从next[j+1]=j开始“验证”。有以下优先判断顺序：
# ~6 z3 M+ F" O  iif(P1…Pj-1 == P2…Pj) => next[j+1]=j
/ V! s. P% `+ `, f' R; eelse if(P1…Pj-2 == P3…Pj) =>next[j+1]=j-1
1 ^3 ]& H- `$ ~0 a' R( q! ^else if(P1…Pj-3 == P4…Pj) =>next[j+1]=j-2
…
…
…
3 l- z# d, P( C4 G  i" g4 Oelse if(P1P2 == Pj-1Pj) => next[j+1]=3
# }- W4 a! @5 h. u& O. }else if(P1 == Pj-1) => next[j+1]=2
4 Y3 y" a' C. P* e) B" w2 ^# ]else if(P1 != Pj-1) => next[j+1]=1
4 g6 z* f4 h* y每次前去尾1个，后掐头1个，直至得到next[j+1]

) V+ _" Q6 G$ {; d+ x1 ]& m' x
: t: F6 g9 N& c$ t: z' }+ k- W再进一步想，next值是一个“工具”，我们单独的求next[j+1]是完全没有意义的，就是说要求next就要把所有j的next求出来。所有一般的，我们都是已知前j个元素的next值，求next[j+1]，以此递推下去，求完整的next数组。
) Y7 r* A- e8 l但是，上面的思考过程还是最根本的。所以问题变为两个：知道前j个元素的next的情况下，
3 o  g6 u" q3 x. m4 c3 Q7 a9 }①next[j+1]的可能的最大值是多少（即从哪开始验证）
/ }* s1 b! J/ x! z②某一步验证失败后，需要“前去尾几个，后掐头几个？”（即本次验证失败后，再验证哪个值）
看一下的分析：
' z: v7 A3 R) h" P
; W8 h$ s4 ~% K9 o
1、next[j+1]的最大值为next[j]+1。
& a$ X2 e) }+ e$ L$ {+ K因为：
假设next[j]=k1，则可以说明P1…Pk1-1=Pj-k1+1…Pj-1，且这是前j个元素最大的首尾重合序列。
* b3 M8 D, G9 r4 g" y: l如果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]
/ w- B/ _: x+ y, l  P9 d4 [这里不好解释，直接看下面的流程分析及图解

1 u- u3 E6 i1 y5 E
$ W% C  @0 Y+ m5 y9 S开——始——划——重——点！
从头走一遍流程
2 W! K* k4 `: P; {$ V2 p- }! @! x. p, X①求next[j+1]，设值为m
1 B% E5 I, V! L6 ]②已知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
⑤第二第三步联合得到:
P1…Pk2-1 = Pk1-k2+1…Pk1-1 = Pj-k1+1…Pk2-k1+j-1 = Pj-k2+1…Pj-1 即四段重合
) ~3 G2 K/ t2 U: @& y/ D: t⑥这时候，再判断如果Pk2=Pj，则P1…Pk2-1P~k2 = Pj-k2+1…Pj-1Pj，则next[j+1]=k2+1；否则再取next[k2]=k3…以此类推


, h$ f, b' {0 W6 p; p- n上面几步，耐心看下来，结合那个式子很容易看懂。最后，再加一个图的模拟帮助理解：
$ ^9 O4 p$ u# x4 j  \1 r1、要求next[k+1] 其中k+1=17
! O+ D/ H/ _6 Y, Y1 A4 ~' V

2、已知next[16]=8，则元素有以下关系：
/ p% @* [1 `' J: g

3、如果P8=P16，则明显next[17]=8+1=9
4、如果不相等，又若next[8]=4，则有以下关系
( `, x* H+ |. H- y: W
) k9 ~3 _' b9 D% n1 ?
6 T, e+ {0 K9 B- K( N9 Y5 |& ^' P+ f又加上2的条件知
: B( r1 o- n* j% B* u- Q
. m/ o  y6 f4 T& w) c0 X) C
- \5 B- {+ I3 w/ z( u7 R6 d主要是为了证明：

  B; X$ t9 x8 @- d& `$ G
5、现在在判断，如果P16=P4则next[17]=4+1=5，否则，在继续递推
6、若next[4]=2，则有以下关系
' c7 l( r7 ~3 `

7、若P16=P2，则next[17]=2+1=3;否则继续取next[2]=1、next[1]=0；遇到0时还没出结果，则递推结束，此时next[17]=1。最后，再返回看那5行算法，应该很容易明白了！
$ ~1 F+ H8 d# t$ B————————————————
+ E# _% `; H5 K' z. `  B2 T5 a版权声明：本文为CSDN博主「Sirm23333」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
6 R, Z0 o: T4 i5 K$ Y1 ?% Z原文链接：https://blog.csdn.net/qq_37969433/article/details/82947411
& P: |4 i% q# T3 a, j% M3 _
* I' H7 v' p* Q6 v" {( h+ X
% y, H: w) Z7 I5 J
' M' d! K/ E0 N: W/ ~7 ?