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

杨利霞

（算法）通俗易懂的字符串匹配KMP算法及求next值算法
7 ]% s+ `, T8 y0 c' B; `
8 {. f9 M0 s2 k9 e大多数据结构课本中，串涉及的内容即串的模式匹配，需要掌握的是朴素算法、KMP算法及next值的求法。在考研备考中，参考严奶奶的教材，我也是在关于求next值的算法中卡了一下午时间，感觉挺有意思的，把一些思考的结果整理出来，与大家一起探讨。


$ O6 u( n1 G; C8 K本文的逻辑顺序为
1、最基本的朴素算法
2、优化的KMP算法
3、应算法需要定义的next值
4、手动写出较短串的next值的方法
5、最难理解的、足足有5行的代码的求next值的算法
所有铺垫为了最后的第5点，我觉得以这个逻辑下来，由果索因还是相对好理解的，下面写的很通俗，略显不专业…
7 [6 P: t. e& n8 g# w; N
4 ]6 V8 B5 x4 Q1 M- ?
一、问题描述
给定一个主串S及一个模式串P，判断模式串是否为主串的子串；若是，返回匹配的第一个元素的位置（序号从1开始），否则返回0；如S=“abcd”，P=“bcd”，则返回2；S=“abcd”，P=“acb”，返回0。
! C4 \) w! ?6 B( S( b. j2 V

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


- Y0 d+ h( q, V8 p* l$ V

这个算法简单，不多说，附上代码
3 q" ]+ C8 R9 j7 e, ?* w

#include<stdio.h>
int Index_1(char s[],int sLen,char p[],int pLen){//s为主串，sLen为主串元素个数，p为模式串，pLen为模式串的个数
, P' O0 ^* r) ?+ `% y0 a, M    if(sLen<pLen)return 0;
3 X6 |, v8 j& C) ?# B. g5 d. E0 T    int i = 1,j = 1;
( n$ v* ^3 N( Z0 N& m: M    while(i<=sLen && j<=pLen){
        if(s==p[j]){i++;j++;}
        else{
( _& A4 Y! V. G+ A- t0 |  Y- G/ Y            i = i-j+2;
            j = 1;
        }
, ?! g2 p! n+ ~    }
    if(j>pLen) return i-pLen;
" l; z3 p7 V+ C- c% o    return 0;
' _: ^( t4 k* F  R5 r}
, s8 N* \; P5 O  `) Y5 Q5 m' kvoid main(){
+ f0 Y' Z9 l5 J9 W! H9 V  L0 {    char s[]={' ','a','b','c','a','b','a','a','a','a','b','a','a','b','c','a','c'};//从序号1开始存
/ {; ^; T6 a' _1 D& x    char p[]={' ','a','b','a','a','b','c','a','c'};
9 B. Y8 \$ `0 u% D& ^    int sLen = sizeof(s)/sizeof(char)-1;
" ^+ v' C1 |. q7 H/ N7 [) R    int pLen = sizeof(p)/sizeof(char)-1;
    printf("%d",Index_1(s,sLen,p,pLen));
& e/ u5 n5 v& Y2 X8 [}
' R: I$ ?5 Z- M( X4 N8 z2 R$ ^* J1
2
" ]- W* Q7 {, _; \" L* a# ?9 b3
8 r# |8 A  X7 k0 {# Z4
$ Z$ z. a! D$ q5 P5
6
9 t7 w2 c8 R, |$ y9 F; O3 @7
' J. G. l, q/ |! J. `9 v8
9
5 I: \' C( i7 A# |7 j4 X6 D/ E10
" N5 Z  [) c1 ]6 O' j) O11
! j% k- Z( `: w6 j" o; U12
13
' w9 Z4 k. r5 N9 v8 s14
  q/ A% m0 ~  w15
16
2 k" v: U7 N" o- p( q% i1 ]17
+ q8 |' z) D6 I, `18
19
20
8 a' G1 j* I/ w' v/ O; l' x21
. b$ ], u0 f7 T9 Z/ m! G三、改进的算法——KMP算法
朴素算法理解简单，但两个串都有依次遍历，时间复杂度为O(n*m)，效率不高。由此有了KMP算法。
一般的，在一次匹配中，我们是不知道主串的内容的，而模式串是我们自己定义的。
朴素算法中，P的第j位失配，默认的把P串后移一位。
% W) {/ m) u# ]' j' R' y- H但在前一轮的比较中，我们已经知道了P的前(j-1)位与S中间对应的某(j-1)个元素已经匹配成功了。这就意味着，在一轮的尝试匹配中，我们get到了主串的部分内容，我们能否利用这些内容，让P多移几位(我认为这就是KMP算法最根本的东西)，减少遍历的趟数呢？答案是肯定的。再看下面改进后的动图：



' r& n3 q9 B( `- W  O& H
/ D3 S3 U9 D/ y# V* h这个模拟过程即KMP算法，若没有看明白，继续往下看相应的解释，理解需要把P多移几位，然后回头再看一遍这个图就很明了了。
2 D( G  ?( x  J2 U

相比朴素算法：
  g* S$ G# H# Q: @  v朴素算法： 每次失配，S串的索引i定位的本次尝试匹配的第一个字符的后一个。P串的索引j定位到1；T(n)=O(n*m)
( v$ t( r5 F( B$ U% i$ S% HKMP算法： 每次失配，S串的索引i不动，P串的索引j定位到某个数。T(n)=O(n+m)，时间效率明显提高

- c' x9 N& q8 B* F' B: R. X" c% [
; z9 f( U" ]* O* \1 s6 e! |而这“定位到某个数”，这个数就是接下来引入的next值。（实际上也就是P往后移多少位，换一种说法罢了：从上图中也可以看出，失配时固定i不变，令S与P[某个数]对齐，实际上是P右移几位的另一种表达，只有为什么这么表达，当然是因为程序好写。）


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

0 E7 i! P. }  p' w% M/ ^( j) b- b
5 H, f& f- E) }比如，Pj处失配，绿色的是Pj，则我们可以确定P1…Pj-1是与Si…Si+j-2相对应的位置一一相等的
3 y8 C' O+ y1 e, }+ }! U% M
) E; H* D: P( ^# T1 C
9 F7 E0 P5 H! f0 |' n% X
6 i, u3 c" Y3 Y% O+ Y5 U假设P1…Pj-1中，P1…Pk-1与Pj-k+1…Pj-1是一一相等的，为了下面说的清楚，我们把这种关系叫做“首尾重合”
& C- F+ A2 q6 y! y9 B

. N2 |) o* f5 M/ z0 R
; ^1 y. q. R2 j* Y% t# C
那么可以推出，P1…Pk-1与Si…Si+j-2


+ h! L0 ~0 c) X' \; n
9 c/ F4 B, w3 ^3 I
显然，接下来要做的就是把模式串右移了，移到哪里就不用多说了：


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

* T- k  H; @/ R0 I  C! U
# L6 V$ L7 q# L1 e  e! D最后，如果我们知道了一个字符串的next值，那么KMP算法也就很好懂了。相比朴素算法，当发生失配时，i不变，j=next[j]就好啦！接下来就是怎么确定next值了。


+ b, u- O. E, h4 ?+ D5 c% \" z四、手动写出一个串的next值
我们规定任何一个串，next[1]=0。(不用next[0]，与串的所有对应)，仍是一张动图搞定问题：


( p7 d* z1 O4 O/ I4 L4 _2 v" z这个扫一眼就能依次写出，会了这个方法，应付个期末考试没问题了。
$ I# Q  s" |3 ?, _$ t+ p) A9 ~4 V$ o
5 u9 `8 V) Q6 M. w6 M  A
通过把next值“看”出来，我们再来分析next值，这就很容易得到超级有名的公式了，这个式子对后面的算法理解很重要！所以先要看懂这个式子，如果上面的内容通下来了，这个应该很容易看懂了：
3 F% z( ?- X6 ]% {" i



五、求next的算法
终于到了最后了~短的串的next值我们可以“看”出来，但长的串就需要借助程序了，具体算法刚接触的时候确实不容易理解，但给我的体验，把上面的内容写完，现在感觉简简单单了…先附上程序再做解释，(终于到了传说中的整整5行代码让我整理了一下午)。
5 Y6 Y) f, \: J( G4 |% Q( d7 S
4 i" `7 O! ]$ E, n" @0 K
4 A8 [0 N4 R+ f7 B/ `' Dint GetNext(char ch[],int cLen,int next[]){//cLen为串ch的长度
( Y, C& h! I) \+ y- s2 n1 _    next[1] = 0;
( p; G. a% X. L  ?" K* C% l: l+ S# J    int i = 1,j = 0;
    while(i<=cLen){
        if(j==0||ch==ch[j]) next[++i] = ++j;
1 l  G4 H6 @# V% v4 s8 Z9 G6 d        else j = next[j];
* ?# _. N3 R8 l0 n    }
1 F9 u- C' e1 t5 x/ L% H. O}
  {3 I8 g' @2 g" E% _) N' j5 B
4 A  k- F3 g8 v还是先由一般再推优化：
3 Y2 b8 E' [. R3 J" Z直接求next[j+1]（至于为什么是j+1，是为了和下面的对应）
根据之前的分析，next[j+1]的值为pj+1的前j个元素的收尾重合的最大个数加一。即需要满足两个条件，把它的值一步步“检验”出来。一是“个数最多”的，因此要从可能的最大值开始验；二是“首尾重合”，因此要一一对应验是否相等。
不难理解，next[j+1]的最大值为j，所有我们从next[j+1]=j开始“验证”。有以下优先判断顺序：
6 i0 w1 K5 Y: W2 vif(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
/ D/ q* o! ?: s! m…
…
/ x% t; C' U3 }7 ^. s2 {) ?* r…
else 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]
; Q0 k" [. F! M! j4 |5 w

再进一步想，next值是一个“工具”，我们单独的求next[j+1]是完全没有意义的，就是说要求next就要把所有j的next求出来。所有一般的，我们都是已知前j个元素的next值，求next[j+1]，以此递推下去，求完整的next数组。
: R" g6 u0 c8 `' l8 a4 ?! \. Y但是，上面的思考过程还是最根本的。所以问题变为两个：知道前j个元素的next的情况下，
( }( X$ l0 n+ \6 K: C/ @4 A①next[j+1]的可能的最大值是多少（即从哪开始验证）
②某一步验证失败后，需要“前去尾几个，后掐头几个？”（即本次验证失败后，再验证哪个值）
看一下的分析：
: E, v( g4 {  |; M
+ R; s$ s  x- I7 u) N
1、next[j+1]的最大值为next[j]+1。
因为：
假设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
0 v8 o) i6 N4 [- z5 n4 C: m2、如果Pk1≠Pj，那么next[j+1]可能的次大值为next[next[j]]+1，以此类推即可高效求出next[j+1]
这里不好解释，直接看下面的流程分析及图解

! x; c0 E3 A6 O8 Y
开——始——划——重——点！
从头走一遍流程
* }$ b; `7 Q- N; L- m①求next[j+1]，设值为m
②已知next[j]=k1，则有P1…Pk1-1 = Pj-k1+1…Pj-1
# B/ |7 H3 ?+ G4 ^; q+ [. \③如果Pk1=Pj，则P1…Pk1-1PK = Pj-k1+1…Pj-1Pj，则next[j+1]=k1+1，否则
: L9 N, S+ N$ i/ x8 B④已知next[k1]=k2，则有P1…Pk2-1 = Pk1-k2+1…Pk1-1
⑤第二第三步联合得到:
& p0 l0 ~  G9 r) u+ sP1…Pk2-1 = Pk1-k2+1…Pk1-1 = Pj-k1+1…Pk2-k1+j-1 = Pj-k2+1…Pj-1 即四段重合
% a3 U4 T  _% c⑥这时候，再判断如果Pk2=Pj，则P1…Pk2-1P~k2 = Pj-k2+1…Pj-1Pj，则next[j+1]=k2+1；否则再取next[k2]=k3…以此类推


* q7 ]1 S1 u0 n8 F上面几步，耐心看下来，结合那个式子很容易看懂。最后，再加一个图的模拟帮助理解：
1、要求next[k+1] 其中k+1=17
2 C! ?1 C( `1 x9 \  w% T

2、已知next[16]=8，则元素有以下关系：
$ `3 \6 V( F4 P+ w5 }$ T: u

! I6 w! t. ~8 `! d2 c3、如果P8=P16，则明显next[17]=8+1=9
4、如果不相等，又若next[8]=4，则有以下关系
0 R6 t2 y2 Y4 B

又加上2的条件知


- ~( R& {3 c/ d6 [主要是为了证明：


5、现在在判断，如果P16=P4则next[17]=4+1=5，否则，在继续递推
% A% j. _$ s5 E+ w2 P0 h7 x  y6、若next[4]=2，则有以下关系
( x0 Z) I6 J1 e: X! a

7、若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版权协议，转载请附上原文出处链接及本声明。
" P: |1 R/ E% f, k' B/ H) Z- C原文链接：https://blog.csdn.net/qq_37969433/article/details/82947411


. g) T: _; n& B0 T2 }; u9 I
- ~' \; M8 ~8 |& l  T, L; S  w$ A