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

杨利霞

（算法）通俗易懂的字符串匹配KMP算法及求next值算法
4 H. G$ m2 _  l
9 S/ Q* R3 f0 }. D大多数据结构课本中，串涉及的内容即串的模式匹配，需要掌握的是朴素算法、KMP算法及next值的求法。在考研备考中，参考严奶奶的教材，我也是在关于求next值的算法中卡了一下午时间，感觉挺有意思的，把一些思考的结果整理出来，与大家一起探讨。
  B0 B# X' I% b1 v8 k

本文的逻辑顺序为
- e5 g, g- f/ e* G( l1、最基本的朴素算法
2、优化的KMP算法
3、应算法需要定义的next值
4、手动写出较短串的next值的方法
5、最难理解的、足足有5行的代码的求next值的算法
' f/ w' N3 }2 `. o9 m6 ?所有铺垫为了最后的第5点，我觉得以这个逻辑下来，由果索因还是相对好理解的，下面写的很通俗，略显不专业…
: Q# `& }5 m  x9 W3 t) ~  b, F

! C, c, i, [6 s一、问题描述
) ^+ j, Y7 h/ F) L* x给定一个主串S及一个模式串P，判断模式串是否为主串的子串；若是，返回匹配的第一个元素的位置（序号从1开始），否则返回0；如S=“abcd”，P=“bcd”，则返回2；S=“abcd”，P=“acb”，返回0。
  N9 D$ ]% H- Y. Q7 ]; s
' X6 c& H% k* A6 S/ w! z
) ?% c& s2 O) d; e! u4 F9 p; Z二、朴素算法
( X& F' L' P# @最简单的方法及一次遍历S与P。以S=“abcabaaaabaaacac”,P="abaabcac"为例，一张动图模拟朴素算法：

- K) H: @: F9 m6 p/ U2 L


这个算法简单，不多说，附上代码
" h5 k1 l% H. p+ b6 T  w
- J- w  G. A& I! m; f/ g! O
% {) N6 Y. s9 E4 x#include<stdio.h>
int Index_1(char s[],int sLen,char p[],int pLen){//s为主串，sLen为主串元素个数，p为模式串，pLen为模式串的个数
! O: s) g0 J) A+ n+ h! F    if(sLen<pLen)return 0;
# @  n; t9 Y. J- \$ p0 T( o4 }" [- X    int i = 1,j = 1;
    while(i<=sLen && j<=pLen){
        if(s==p[j]){i++;j++;}
        else{
* s/ [! o+ {5 E6 C- p# _            i = i-j+2;
4 o! J: l3 C2 I1 u            j = 1;
& P% @, F! J3 R5 h  s        }
    }
& y" e+ Z2 Y) |+ j' H/ p: {    if(j>pLen) return i-pLen;
    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'};
    int sLen = sizeof(s)/sizeof(char)-1;
) O, \' v! m+ T5 s, c9 ^; z. A# z: {8 O    int pLen = sizeof(p)/sizeof(char)-1;
$ m; `1 j2 m# D& K& G5 }. J5 X4 U    printf("%d",Index_1(s,sLen,p,pLen));
}
1
1 N7 |+ {8 ?: [+ Y2
3
% L- b& H6 h: f- V6 g4
5
" t9 }( b# Y' \! f1 F7 e9 H" H6
7
! x+ w7 p! i$ c7 g7 n( Q/ c8
+ n" \& n/ i: l  v- {9
: j1 Q" D, D, ^! ]' l, H. r2 m10
: _" M$ I5 x4 \: _11
- O2 ~  {. h& w" g2 a; `+ ^12
; H( M$ M- x/ K13
2 ]9 S8 x6 l6 D6 O5 r" |14
6 b- w- }! d5 N( w' a1 P2 @15
16
17
# k5 [; i/ [7 u% Y2 K18
5 J$ u1 T1 k$ I' j2 y19
: H1 d" N8 k, {6 k1 ^* g20
. j  B8 ]+ r" w+ B0 Y& m/ h( w21
三、改进的算法——KMP算法
朴素算法理解简单，但两个串都有依次遍历，时间复杂度为O(n*m)，效率不高。由此有了KMP算法。
2 S$ f* a$ i) U7 M  {一般的，在一次匹配中，我们是不知道主串的内容的，而模式串是我们自己定义的。
朴素算法中，P的第j位失配，默认的把P串后移一位。
但在前一轮的比较中，我们已经知道了P的前(j-1)位与S中间对应的某(j-1)个元素已经匹配成功了。这就意味着，在一轮的尝试匹配中，我们get到了主串的部分内容，我们能否利用这些内容，让P多移几位(我认为这就是KMP算法最根本的东西)，减少遍历的趟数呢？答案是肯定的。再看下面改进后的动图：

  w0 d) i9 Q# R% G
4 i& X' U. Z4 a
) a- _" Z/ w5 _/ h
. x2 z/ B! A) U- l( F0 ?这个模拟过程即KMP算法，若没有看明白，继续往下看相应的解释，理解需要把P多移几位，然后回头再看一遍这个图就很明了了。
/ Q+ X$ C  Q  F+ U: T% S& z' ?
, K& S7 C* d$ j$ ^4 \; ^; m! k9 N
' V- R7 \3 {0 \! Y# U- H相比朴素算法：
+ A$ A8 T; p% n7 f+ D/ l( W朴素算法： 每次失配，S串的索引i定位的本次尝试匹配的第一个字符的后一个。P串的索引j定位到1；T(n)=O(n*m)
KMP算法： 每次失配，S串的索引i不动，P串的索引j定位到某个数。T(n)=O(n+m)，时间效率明显提高

, P6 f9 \+ @& K) j8 t
: a3 _# S0 t- Z- K6 I% q! |- x+ N而这“定位到某个数”，这个数就是接下来引入的next值。（实际上也就是P往后移多少位，换一种说法罢了：从上图中也可以看出，失配时固定i不变，令S与P[某个数]对齐，实际上是P右移几位的另一种表达，只有为什么这么表达，当然是因为程序好写。）
7 D0 T% c. Q2 t, [, K. a

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


1 N5 w+ X$ q( v7 b8 _+ i& L比如，Pj处失配，绿色的是Pj，则我们可以确定P1…Pj-1是与Si…Si+j-2相对应的位置一一相等的
% G* Y# m$ m- }0 t  A  M


  g' I; |! J* r3 x/ R假设P1…Pj-1中，P1…Pk-1与Pj-k+1…Pj-1是一一相等的，为了下面说的清楚，我们把这种关系叫做“首尾重合”


; N; a( z5 ?. w! a- V9 r  n
, g5 h- J& v' w- |2 n
: m3 j% P& v1 O& S# s7 U那么可以推出，P1…Pk-1与Si…Si+j-2
! ~% d; b1 r# b- G' P( g# `
! W( q) v5 s, k1 x4 z


7 l8 _: Q4 s, r% P( s8 W) O7 ]显然，接下来要做的就是把模式串右移了，移到哪里就不用多说了：

( A: C; D& @) V. m1 k


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

/ h6 z6 u" A9 C: N1 z
最后，如果我们知道了一个字符串的next值，那么KMP算法也就很好懂了。相比朴素算法，当发生失配时，i不变，j=next[j]就好啦！接下来就是怎么确定next值了。
& W3 W. v+ |/ ~- ?5 K1 F

* M8 }% u- b7 Z& ^/ T1 N6 c四、手动写出一个串的next值
% A: U$ J5 n" C; `' ~! M我们规定任何一个串，next[1]=0。(不用next[0]，与串的所有对应)，仍是一张动图搞定问题：

- b1 p; N; ]" W) A
这个扫一眼就能依次写出，会了这个方法，应付个期末考试没问题了。
! e4 I" V' C7 J# B- o. a

7 V% Z, R: B9 [通过把next值“看”出来，我们再来分析next值，这就很容易得到超级有名的公式了，这个式子对后面的算法理解很重要！所以先要看懂这个式子，如果上面的内容通下来了，这个应该很容易看懂了：
* w1 S$ }& Q5 K. y7 _" B: m+ m
/ ]* M$ z5 V+ x
! A. ^$ f! U  \5 E

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

int GetNext(char ch[],int cLen,int next[]){//cLen为串ch的长度
( y2 H' F; F" v& Q, I    next[1] = 0;
    int i = 1,j = 0;
. k5 |: `8 i1 ]7 [0 G6 N# m0 s    while(i<=cLen){
0 j' ]' b, \0 [1 g# J        if(j==0||ch==ch[j]) next[++i] = ++j;
* D5 v" \3 y1 ^, }* _2 n        else j = next[j];
. W- y* e! q9 U2 k" _8 W    }
3 d3 v) d; ~3 ]2 b' i}
1 W0 C: v5 B1 K( f; ?5 O
还是先由一般再推优化：
0 {5 t- e, l0 ~" C: a& w) j直接求next[j+1]（至于为什么是j+1，是为了和下面的对应）
4 M) T/ m# X$ @) p  O3 U根据之前的分析，next[j+1]的值为pj+1的前j个元素的收尾重合的最大个数加一。即需要满足两个条件，把它的值一步步“检验”出来。一是“个数最多”的，因此要从可能的最大值开始验；二是“首尾重合”，因此要一一对应验是否相等。
* X, i5 P. a6 {; I3 Y不难理解，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
" y0 W. e2 x% G: q…
, K/ o. t$ P) N…
…
! n# c& n' M( h# W  z  F+ r6 oelse if(P1P2 == Pj-1Pj) => next[j+1]=3
+ a; B) O* N/ K' [4 _5 telse if(P1 == Pj-1) => next[j+1]=2
8 q$ l( k- o' ?* t) e, O- xelse if(P1 != Pj-1) => next[j+1]=1
每次前去尾1个，后掐头1个，直至得到next[j+1]
% v5 _+ V' k& y4 p( @  S

再进一步想，next值是一个“工具”，我们单独的求next[j+1]是完全没有意义的，就是说要求next就要把所有j的next求出来。所有一般的，我们都是已知前j个元素的next值，求next[j+1]，以此递推下去，求完整的next数组。
0 @/ t/ d/ ^7 J1 O但是，上面的思考过程还是最根本的。所以问题变为两个：知道前j个元素的next的情况下，
) N, @0 e; }3 R# K①next[j+1]的可能的最大值是多少（即从哪开始验证）
; I; d) ~  O! A②某一步验证失败后，需要“前去尾几个，后掐头几个？”（即本次验证失败后，再验证哪个值）
: p( r3 q- g3 W( q: W9 x# H1 A看一下的分析：
* M: ]7 r4 x0 |# D8 C1 D8 ~4 ^

1、next[j+1]的最大值为next[j]+1。
4 s1 |# P  m  _, c9 a( s7 B  u因为：
1 `4 y, D2 C- `4 B# Y) I假设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
2、如果Pk1≠Pj，那么next[j+1]可能的次大值为next[next[j]]+1，以此类推即可高效求出next[j+1]
这里不好解释，直接看下面的流程分析及图解


开——始——划——重——点！
. Z# J# P/ N$ e" b5 ]从头走一遍流程
& S  x0 ^/ h; \/ y4 S2 I# I①求next[j+1]，设值为m
* G2 L9 H# m1 l/ o# n②已知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
" ~  c( Z) F0 g8 I: E. o7 b⑤第二第三步联合得到:
3 ?" U) B% t7 s( Q# f  hP1…Pk2-1 = Pk1-k2+1…Pk1-1 = Pj-k1+1…Pk2-k1+j-1 = Pj-k2+1…Pj-1 即四段重合
  l# Q3 e4 R5 J% ?⑥这时候，再判断如果Pk2=Pj，则P1…Pk2-1P~k2 = Pj-k2+1…Pj-1Pj，则next[j+1]=k2+1；否则再取next[k2]=k3…以此类推

; F; |$ G, W3 \' {0 R0 v
% [; x0 @# \* ?+ g5 b- m上面几步，耐心看下来，结合那个式子很容易看懂。最后，再加一个图的模拟帮助理解：
# W; z, p3 S7 S9 m; \8 Z% J8 F. P1、要求next[k+1] 其中k+1=17


- _1 x( J7 z% A3 s& J" a/ G2、已知next[16]=8，则元素有以下关系：


, S/ y1 V* S; i+ Y3、如果P8=P16，则明显next[17]=8+1=9
& w* I8 @9 Y" @6 a4 O' M/ v5 {6 f4、如果不相等，又若next[8]=4，则有以下关系


6 T! J$ O7 W, w. x2 K又加上2的条件知
( D  p; V( W7 K6 a, M; x7 d

; p; p& h6 h* _  d+ ^主要是为了证明：


5、现在在判断，如果P16=P4则next[17]=4+1=5，否则，在继续递推
6、若next[4]=2，则有以下关系


7、若P16=P2，则next[17]=2+1=3;否则继续取next[2]=1、next[1]=0；遇到0时还没出结果，则递推结束，此时next[17]=1。最后，再返回看那5行算法，应该很容易明白了！
& A% [9 y" o$ H9 q0 q————————————————
0 f' y& g: s3 Z5 C版权声明：本文为CSDN博主「Sirm23333」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
0 U5 E( z& X7 d: s# u+ F* a3 s原文链接：https://blog.csdn.net/qq_37969433/article/details/82947411
9 F2 {& [! K' I/ q

2 G) h" p6 r( b4 ~! ]. B
9 J8 k7 e( y0 P! f1 [. n: T% L) v5 [" k