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

杨利霞

（算法）通俗易懂的字符串匹配KMP算法及求next值算法
- q" }6 q9 s" @! \3 h  b
大多数据结构课本中，串涉及的内容即串的模式匹配，需要掌握的是朴素算法、KMP算法及next值的求法。在考研备考中，参考严奶奶的教材，我也是在关于求next值的算法中卡了一下午时间，感觉挺有意思的，把一些思考的结果整理出来，与大家一起探讨。
4 e! K, w0 e# v1 x) J

2 L" u  i9 I" r9 Y# O本文的逻辑顺序为
# l& O+ |5 S* |# ]1、最基本的朴素算法
2、优化的KMP算法
1 Z  g0 W! a* V7 j6 |% A1 g3、应算法需要定义的next值
5 V9 f9 N1 n9 ~# [8 f( f4、手动写出较短串的next值的方法
; E) M% E/ B7 K, r. j) Z$ W5、最难理解的、足足有5行的代码的求next值的算法
- a$ o( d/ l- O, x8 y* L所有铺垫为了最后的第5点，我觉得以这个逻辑下来，由果索因还是相对好理解的，下面写的很通俗，略显不专业…
+ y7 A! C5 c7 N6 a6 }/ ~& }+ I* ^

) u. c2 H! \7 a" f- t2 B9 c' U一、问题描述
给定一个主串S及一个模式串P，判断模式串是否为主串的子串；若是，返回匹配的第一个元素的位置（序号从1开始），否则返回0；如S=“abcd”，P=“bcd”，则返回2；S=“abcd”，P=“acb”，返回0。
6 S3 m6 V' D* z% W* I& s* V( n
3 t* ?, E  r  G. ]  z
) K2 F# Q* ?8 @' l: f二、朴素算法
3 @' _/ S! s2 \; A& e( k/ [7 C最简单的方法及一次遍历S与P。以S=“abcabaaaabaaacac”,P="abaabcac"为例，一张动图模拟朴素算法：
, \3 Z" y! M) a9 V, F( P' M- Z) k
3 T  h, v6 Z% @  t
- e1 z% k& ?4 Y; U( i1 m5 F! f

0 W0 O" w' l9 C2 n5 p0 a这个算法简单，不多说，附上代码
0 z  Q3 e, ?3 l
4 k1 H& r$ t- `6 r
) u9 I. g. X5 u  Y. Y3 ~1 o# g9 N#include<stdio.h>
int Index_1(char s[],int sLen,char p[],int pLen){//s为主串，sLen为主串元素个数，p为模式串，pLen为模式串的个数
    if(sLen<pLen)return 0;
  M! c1 G; {5 s$ i3 i/ j    int i = 1,j = 1;
0 a- S% O- j% w  l3 X    while(i<=sLen && j<=pLen){
        if(s==p[j]){i++;j++;}
        else{
            i = i-j+2;
            j = 1;
/ n, h2 m! H! L+ F) y+ Y7 I# X        }
: g* h! {9 F; m( k% {9 |1 O' Z" u    }
0 P" W* [2 }+ x+ Z% C1 H, F. [    if(j>pLen) return i-pLen;
( i" k( T; a. J  P    return 0;
}
void 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'};
; \8 [4 l5 C$ N+ T# u    int sLen = sizeof(s)/sizeof(char)-1;
    int pLen = sizeof(p)/sizeof(char)-1;
6 Y/ r8 x$ t5 [' @! S# w  B$ N    printf("%d",Index_1(s,sLen,p,pLen));
}
1
2
8 k" a6 `; H- Q& x! \& V3
4
4 i) S' {; C9 ?: |" X5
6
7
8
9
8 Y/ k' g8 W+ S! l  e0 a  s0 z10
11
* X, t9 L, O' T2 U" u, u12
13
14
9 L9 v: M" N1 i) ~$ }15
* r6 L/ g8 c: }, J$ K4 u5 s# {16
17
$ F5 Y# M( k5 t2 p. e( m; s6 Z18
19
4 ]+ I7 r* R& Z- y20
21
三、改进的算法——KMP算法
朴素算法理解简单，但两个串都有依次遍历，时间复杂度为O(n*m)，效率不高。由此有了KMP算法。
; x- y- }$ Z; I/ H' E& Z# D$ P一般的，在一次匹配中，我们是不知道主串的内容的，而模式串是我们自己定义的。
, _5 S+ x7 z. R  g朴素算法中，P的第j位失配，默认的把P串后移一位。
但在前一轮的比较中，我们已经知道了P的前(j-1)位与S中间对应的某(j-1)个元素已经匹配成功了。这就意味着，在一轮的尝试匹配中，我们get到了主串的部分内容，我们能否利用这些内容，让P多移几位(我认为这就是KMP算法最根本的东西)，减少遍历的趟数呢？答案是肯定的。再看下面改进后的动图：




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


. D# [! ^8 L. x, ~5 f: }相比朴素算法：
朴素算法： 每次失配，S串的索引i定位的本次尝试匹配的第一个字符的后一个。P串的索引j定位到1；T(n)=O(n*m)
KMP算法： 每次失配，S串的索引i不动，P串的索引j定位到某个数。T(n)=O(n+m)，时间效率明显提高
" h; ?. k2 u- t' e9 O
$ l3 ]: C9 Q* z& |7 m3 f: A& a
7 T: m% T2 x8 q, X而这“定位到某个数”，这个数就是接下来引入的next值。（实际上也就是P往后移多少位，换一种说法罢了：从上图中也可以看出，失配时固定i不变，令S与P[某个数]对齐，实际上是P右移几位的另一种表达，只有为什么这么表达，当然是因为程序好写。）
7 Z8 T2 W6 W( A/ |4 V

% z8 h% e# z; F: v  }) x6 u开——始——划——重——点！（图对逻辑关系比较好理解，但i和j的关系对后面求next的算法好理解！）
: k/ J( c2 E- P( M$ y1 F. F5 Q
; D) k1 ]1 J$ i
( u( I- Y8 C4 G; Q7 l* S比如，Pj处失配，绿色的是Pj，则我们可以确定P1…Pj-1是与Si…Si+j-2相对应的位置一一相等的
0 ~- \+ N( I+ z1 X- [3 e7 R6 ~5 i
2 z2 `$ |; @( Q) }
+ U4 m0 I  U; D9 c
6 @$ ~# P! ?1 x( E8 b假设P1…Pj-1中，P1…Pk-1与Pj-k+1…Pj-1是一一相等的，为了下面说的清楚，我们把这种关系叫做“首尾重合”

% U2 ?7 q2 W# j2 w
  h& `, b, n" Y& ^
  C( }/ F: r4 t1 l* A
4 H4 ^" Z! {: t5 t9 B$ N$ f那么可以推出，P1…Pk-1与Si…Si+j-2



6 {. ?1 r3 i# V3 P* j" E+ E( o# k
! T- W# h! l! o' t3 }* @. d6 P. X显然，接下来要做的就是把模式串右移了，移到哪里就不用多说了：


* Y% W. A! ~8 V4 R. c% j, Z

5 j" P2 U: w& z9 R; O: u5 Q为了表示下一轮比较j定位的地方，我们将其定义为next[j]，next[j]就是第j个元素前j-1个元素首尾重合部分个数加一，当然，为了能遍历完整，首尾重合部分的元素个数应取到最多，即next[j]应取尽量大的值，原因挺好理解的，可以想个例子模拟一下，会完美跳过正确结果。在上图中就是绿色元素的next值为蓝色元素的序号。也即，对于字符串P，next[8]=4。如此，再看一下上面的动图是不是清楚了不少。
) d- N! s7 b4 J: a0 t$ y; l
9 t. ~" J& o' T, t; C! _
最后，如果我们知道了一个字符串的next值，那么KMP算法也就很好懂了。相比朴素算法，当发生失配时，i不变，j=next[j]就好啦！接下来就是怎么确定next值了。
( M( M% F7 D& R* X2 F* p

5 x$ `. c( Q, o- h8 @四、手动写出一个串的next值
我们规定任何一个串，next[1]=0。(不用next[0]，与串的所有对应)，仍是一张动图搞定问题：
! o5 S  o! L& O. f

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

( F. a( K2 J% _/ G$ p( c, L
通过把next值“看”出来，我们再来分析next值，这就很容易得到超级有名的公式了，这个式子对后面的算法理解很重要！所以先要看懂这个式子，如果上面的内容通下来了，这个应该很容易看懂了：

7 V! a4 e% K* H$ {% q, ?3 m3 o
) o6 T( k: _1 N$ U4 x7 |9 W

五、求next的算法
( S( F/ _: y( ^+ y! r终于到了最后了~短的串的next值我们可以“看”出来，但长的串就需要借助程序了，具体算法刚接触的时候确实不容易理解，但给我的体验，把上面的内容写完，现在感觉简简单单了…先附上程序再做解释，(终于到了传说中的整整5行代码让我整理了一下午)。
( r3 S5 V; e( y2 l; m
- b: t: W& e- t3 ~- [
int GetNext(char ch[],int cLen,int next[]){//cLen为串ch的长度
    next[1] = 0;
; W; \0 K1 x8 L* i2 h    int i = 1,j = 0;
; ~' {6 x# y1 z1 j5 a/ j    while(i<=cLen){
        if(j==0||ch==ch[j]) next[++i] = ++j;
! t/ p& N$ i, U4 W        else j = next[j];
/ L$ s1 u0 g, `- c  ]3 c+ F    }
# K$ k( v& |) K  y}

( t9 g2 h0 e2 m4 a$ K0 k还是先由一般再推优化：
直接求next[j+1]（至于为什么是j+1，是为了和下面的对应）
根据之前的分析，next[j+1]的值为pj+1的前j个元素的收尾重合的最大个数加一。即需要满足两个条件，把它的值一步步“检验”出来。一是“个数最多”的，因此要从可能的最大值开始验；二是“首尾重合”，因此要一一对应验是否相等。
! b4 f' `% K- ^; f1 ]不难理解，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
; i9 d3 q9 ~$ b% n) |3 u- […
# N5 m! ]6 c  X+ H$ e8 q2 I…
, m+ ^+ u9 N0 r+ E4 O$ x9 M2 x, O…
9 Y4 K, I: N# y$ ^* S: C' |1 helse if(P1P2 == Pj-1Pj) => next[j+1]=3
else if(P1 == Pj-1) => next[j+1]=2
& @. l# ^- z* k( Uelse if(P1 != Pj-1) => next[j+1]=1
每次前去尾1个，后掐头1个，直至得到next[j+1]
9 j# x2 _9 r8 ?& u( X- a
* v, U0 J' t# b+ l; c
7 s( m" B* o3 _; A! r$ s再进一步想，next值是一个“工具”，我们单独的求next[j+1]是完全没有意义的，就是说要求next就要把所有j的next求出来。所有一般的，我们都是已知前j个元素的next值，求next[j+1]，以此递推下去，求完整的next数组。
% P' p5 ~- T& l但是，上面的思考过程还是最根本的。所以问题变为两个：知道前j个元素的next的情况下，
①next[j+1]的可能的最大值是多少（即从哪开始验证）
2 G% N4 T0 k! g0 |: e! |  w% L- p②某一步验证失败后，需要“前去尾几个，后掐头几个？”（即本次验证失败后，再验证哪个值）
& V. k, [3 q1 G. A' c看一下的分析：
# i* W: F( w6 j( t3 j% O  N
) C. F% m8 @$ O" H; n; [
7 F9 l0 S& p( y2 S* |% B1、next[j+1]的最大值为next[j]+1。
因为：
; c$ j/ R! ]; L; S0 B# e+ Q假设next[j]=k1，则可以说明P1…Pk1-1=Pj-k1+1…Pj-1，且这是前j个元素最大的首尾重合序列。
* e$ q3 s! y# w, A4 e8 {: c9 c如果Pk1=Pj，那么P1…Pk1-1PK=Pj-k1+1…Pj-1Pj，那么k+1这也是前j+1个元素的最大首尾重合序列，也即next[j+1]的值为k1+1
2 d# q2 ?2 z9 m3 [2、如果Pk1≠Pj，那么next[j+1]可能的次大值为next[next[j]]+1，以此类推即可高效求出next[j+1]
2 F5 m, Z" Z$ Q  c6 d这里不好解释，直接看下面的流程分析及图解


7 d4 P, g$ C9 S. Z8 a! G& j; v开——始——划——重——点！
+ l' Y+ ]; {. ~( Y( ?0 e从头走一遍流程
2 p, O+ q( J; Q. E3 v. {①求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，否则
④已知next[k1]=k2，则有P1…Pk2-1 = Pk1-k2+1…Pk1-1
⑤第二第三步联合得到:
/ ~/ m* `- q# y" `4 PP1…Pk2-1 = Pk1-k2+1…Pk1-1 = Pj-k1+1…Pk2-k1+j-1 = Pj-k2+1…Pj-1 即四段重合
6 Y7 I3 y  P! ]⑥这时候，再判断如果Pk2=Pj，则P1…Pk2-1P~k2 = Pj-k2+1…Pj-1Pj，则next[j+1]=k2+1；否则再取next[k2]=k3…以此类推
3 R2 q5 Y( J1 c7 t+ K& [% K" r
, w1 _% `) X& N9 G& m
0 R. F) Q/ I' K, B) H, G2 |4 ]上面几步，耐心看下来，结合那个式子很容易看懂。最后，再加一个图的模拟帮助理解：
& B1 f5 O  \+ N9 X; p% }1、要求next[k+1] 其中k+1=17
/ p2 x0 {, v! s. e0 Q, r6 P/ c% k$ j! @

2、已知next[16]=8，则元素有以下关系：
7 d7 Q/ N& ~2 e5 H) x* s

0 [' N- B* L  i+ m3、如果P8=P16，则明显next[17]=8+1=9
4、如果不相等，又若next[8]=4，则有以下关系
0 b' z5 ]) h3 t6 p/ `
+ B. k; {; A; |$ d; s5 Z! a2 l2 [6 f7 d
# y0 t/ q1 b" S( ]  ]1 X1 F( i又加上2的条件知


! N% j* P, A) d: U$ Y( B1 w主要是为了证明：

! T) b3 f7 a  }4 I: t
5、现在在判断，如果P16=P4则next[17]=4+1=5，否则，在继续递推
; [2 E) F+ p! G# c% C7 V6、若next[4]=2，则有以下关系
  v, V4 J' x/ O1 u" j
( g9 @" u% E# h5 d: w) `
' N9 A) j( n1 ~8 a/ I2 W" g5 b7、若P16=P2，则next[17]=2+1=3;否则继续取next[2]=1、next[1]=0；遇到0时还没出结果，则递推结束，此时next[17]=1。最后，再返回看那5行算法，应该很容易明白了！
. U: X) {' Q6 [————————————————
) I6 A  z7 x% m8 x& {% Y* \0 ?版权声明：本文为CSDN博主「Sirm23333」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
" o* P7 e5 d) y' l& M4 Y原文链接：https://blog.csdn.net/qq_37969433/article/details/82947411
' U7 q- ?" Q% o* A$ f3 S
; n1 V- ~. n; R) ?- T( ~# K
6 I1 c! J: h$ U% t9 B) W9 G  O6 H
" N1 o8 F! n' ?+ }/ P) u! A) M