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

杨利霞

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

. F- f4 m* @' g" L7 A6 K大多数据结构课本中，串涉及的内容即串的模式匹配，需要掌握的是朴素算法、KMP算法及next值的求法。在考研备考中，参考严奶奶的教材，我也是在关于求next值的算法中卡了一下午时间，感觉挺有意思的，把一些思考的结果整理出来，与大家一起探讨。
3 _7 t% `3 H' O  v3 @( L( M

/ ~$ M# O6 y( m3 L' y. N本文的逻辑顺序为
1、最基本的朴素算法
9 K8 b4 S" j( ]' ~) r2、优化的KMP算法
3、应算法需要定义的next值
4、手动写出较短串的next值的方法
5、最难理解的、足足有5行的代码的求next值的算法
所有铺垫为了最后的第5点，我觉得以这个逻辑下来，由果索因还是相对好理解的，下面写的很通俗，略显不专业…


一、问题描述
9 I5 V! o% f7 y* H给定一个主串S及一个模式串P，判断模式串是否为主串的子串；若是，返回匹配的第一个元素的位置（序号从1开始），否则返回0；如S=“abcd”，P=“bcd”，则返回2；S=“abcd”，P=“acb”，返回0。
) O2 m) A$ H4 `9 R  z+ m
8 L0 U8 {3 c8 u2 g2 z
二、朴素算法
* f0 x( s* L$ z3 ~/ O8 f" t) i8 D最简单的方法及一次遍历S与P。以S=“abcabaaaabaaacac”,P="abaabcac"为例，一张动图模拟朴素算法：

* {" \! \+ K" ?' J

3 ?) f! z, {# k* u" a) E1 d/ |1 W) P
这个算法简单，不多说，附上代码
3 D3 \1 ^* c9 D# I  x

% u( ]& T" ?  H+ C#include<stdio.h>
int Index_1(char s[],int sLen,char p[],int pLen){//s为主串，sLen为主串元素个数，p为模式串，pLen为模式串的个数
( Q5 k4 q5 B$ ^9 o0 Y- w. a    if(sLen<pLen)return 0;
6 ?6 Z" Q, M  b. A! c8 Z3 d& P    int i = 1,j = 1;
    while(i<=sLen && j<=pLen){
& h% M4 P/ a/ f3 X        if(s==p[j]){i++;j++;}
        else{
            i = i-j+2;
            j = 1;
        }
    }
. S4 a' V3 L* \7 D4 ~    if(j>pLen) return i-pLen;
    return 0;
" {- a% ~. t  V) C3 ^4 G}
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'};
" M" z9 `2 S& f$ H5 i, z    int sLen = sizeof(s)/sizeof(char)-1;
  W  s6 c/ H5 H0 l7 B0 ]    int pLen = sizeof(p)/sizeof(char)-1;
% H: j1 K, M( T, I    printf("%d",Index_1(s,sLen,p,pLen));
* `/ U, g7 _( C9 T0 T- ?}
* J% b- x" ]! a, I5 _1 R) i1
2
/ Y+ L% l9 ^9 u, Q8 L3 O3
4
, l' N1 j4 A, y3 O2 i5
1 }/ \# {# E, r5 y6
  ~) c8 B2 f9 ?; ~7
8
+ u& v$ o5 B  O& p9
10
11
12
3 V! R4 a( v6 m8 `: b* ?7 R13
/ `& ?0 k' T/ c: k' L- y14
. a8 d  ~- Z2 q$ v15
16
17
18
) Q0 W3 s/ ?6 ~$ y& k19
20
" `- r/ \9 k# t$ O21
三、改进的算法——KMP算法
朴素算法理解简单，但两个串都有依次遍历，时间复杂度为O(n*m)，效率不高。由此有了KMP算法。
一般的，在一次匹配中，我们是不知道主串的内容的，而模式串是我们自己定义的。
5 z5 v+ v7 H4 G5 a  X朴素算法中，P的第j位失配，默认的把P串后移一位。
但在前一轮的比较中，我们已经知道了P的前(j-1)位与S中间对应的某(j-1)个元素已经匹配成功了。这就意味着，在一轮的尝试匹配中，我们get到了主串的部分内容，我们能否利用这些内容，让P多移几位(我认为这就是KMP算法最根本的东西)，减少遍历的趟数呢？答案是肯定的。再看下面改进后的动图：

6 i, ?' S& `/ `! F

: E4 ?1 I( d( T5 D. |- m8 N$ m* M
这个模拟过程即KMP算法，若没有看明白，继续往下看相应的解释，理解需要把P多移几位，然后回头再看一遍这个图就很明了了。
8 N3 {/ g) G$ o  @7 k. @8 `- h
; I6 [2 b* K9 C8 @
0 c+ U: m4 O5 `0 {+ ], f相比朴素算法：
朴素算法： 每次失配，S串的索引i定位的本次尝试匹配的第一个字符的后一个。P串的索引j定位到1；T(n)=O(n*m)
KMP算法： 每次失配，S串的索引i不动，P串的索引j定位到某个数。T(n)=O(n+m)，时间效率明显提高


3 C( ?# x% e8 P( q  \而这“定位到某个数”，这个数就是接下来引入的next值。（实际上也就是P往后移多少位，换一种说法罢了：从上图中也可以看出，失配时固定i不变，令S与P[某个数]对齐，实际上是P右移几位的另一种表达，只有为什么这么表达，当然是因为程序好写。）
* ~: s; l4 {7 |6 F4 [

开——始——划——重——点！（图对逻辑关系比较好理解，但i和j的关系对后面求next的算法好理解！）
( m3 p" b8 B* ~5 z) n* N8 `

( d! `5 Y- Z9 X0 U: q& _4 q7 c比如，Pj处失配，绿色的是Pj，则我们可以确定P1…Pj-1是与Si…Si+j-2相对应的位置一一相等的

5 {" Q/ y$ J3 L) \$ n
% e9 @, m) C, \: A& o
假设P1…Pj-1中，P1…Pk-1与Pj-k+1…Pj-1是一一相等的，为了下面说的清楚，我们把这种关系叫做“首尾重合”
& |6 ?( u0 a3 j) {+ i
8 A4 M& Z  c( q' Q

2 u& C' n0 U& Z! X' Q* }  @6 G* s" t
3 x3 u1 j# p  c那么可以推出，P1…Pk-1与Si…Si+j-2
9 S3 q$ M+ C# G- k$ q

) }# f+ i) J1 h3 n- n

显然，接下来要做的就是把模式串右移了，移到哪里就不用多说了：
) Z/ J6 A% ]" R; _9 x3 Q
$ _1 h4 Z$ S9 D* x4 _' x
0 N  R1 B* n5 h2 a" F3 Y
: F" ^  p! O' m; N4 Y  z  i$ X7 x
为了表示下一轮比较j定位的地方，我们将其定义为next[j]，next[j]就是第j个元素前j-1个元素首尾重合部分个数加一，当然，为了能遍历完整，首尾重合部分的元素个数应取到最多，即next[j]应取尽量大的值，原因挺好理解的，可以想个例子模拟一下，会完美跳过正确结果。在上图中就是绿色元素的next值为蓝色元素的序号。也即，对于字符串P，next[8]=4。如此，再看一下上面的动图是不是清楚了不少。
) X' i! A" \4 r5 x( I$ E

最后，如果我们知道了一个字符串的next值，那么KMP算法也就很好懂了。相比朴素算法，当发生失配时，i不变，j=next[j]就好啦！接下来就是怎么确定next值了。
7 K2 P- S- R+ u

$ E* @4 n. \/ W四、手动写出一个串的next值
" Z. T# ?( [& b% Y8 b- E; j我们规定任何一个串，next[1]=0。(不用next[0]，与串的所有对应)，仍是一张动图搞定问题：

( V+ h; |. g. z2 D
% y7 V& k: C9 [3 P3 r% u5 N- S( [这个扫一眼就能依次写出，会了这个方法，应付个期末考试没问题了。


  ?% a  W5 b7 ?% z7 X通过把next值“看”出来，我们再来分析next值，这就很容易得到超级有名的公式了，这个式子对后面的算法理解很重要！所以先要看懂这个式子，如果上面的内容通下来了，这个应该很容易看懂了：
5 N, O2 c9 J! N6 O7 ]

$ \7 q& z1 t$ P" r

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

/ D( e: f. V* Y. w6 n4 h
int GetNext(char ch[],int cLen,int next[]){//cLen为串ch的长度
2 P2 N: U, R  l    next[1] = 0;
# a% y3 k/ f/ Z# G: D+ J6 r    int i = 1,j = 0;
    while(i<=cLen){
        if(j==0||ch==ch[j]) next[++i] = ++j;
7 `& ]8 g* B$ d4 @9 B        else j = next[j];
3 T% X; f: `3 k0 p  F2 F1 {    }
$ b  O; P* r, h( s( n+ C}
' f0 t5 t7 s7 }, R. h) g" t
' E- k0 |2 [+ @还是先由一般再推优化：
直接求next[j+1]（至于为什么是j+1，是为了和下面的对应）
* u  S% T) s& U* i5 P, Y) y' s# d% C& D根据之前的分析，next[j+1]的值为pj+1的前j个元素的收尾重合的最大个数加一。即需要满足两个条件，把它的值一步步“检验”出来。一是“个数最多”的，因此要从可能的最大值开始验；二是“首尾重合”，因此要一一对应验是否相等。
不难理解，next[j+1]的最大值为j，所有我们从next[j+1]=j开始“验证”。有以下优先判断顺序：
if(P1…Pj-1 == P2…Pj) => next[j+1]=j
% B" K' w  K0 _: I8 Celse if(P1…Pj-2 == P3…Pj) =>next[j+1]=j-1
else if(P1…Pj-3 == P4…Pj) =>next[j+1]=j-2
…
…
* t- ^0 O7 G: a- ]8 l…
5 b2 p. H) V+ H/ Melse if(P1P2 == Pj-1Pj) => next[j+1]=3
4 L! f: s5 o! M! B, U7 zelse if(P1 == Pj-1) => next[j+1]=2
9 f: t7 p8 k& [else if(P1 != Pj-1) => next[j+1]=1
& c" a8 u6 _$ V4 a每次前去尾1个，后掐头1个，直至得到next[j+1]
- G2 u' }7 z; |+ ?

再进一步想，next值是一个“工具”，我们单独的求next[j+1]是完全没有意义的，就是说要求next就要把所有j的next求出来。所有一般的，我们都是已知前j个元素的next值，求next[j+1]，以此递推下去，求完整的next数组。
/ ]# Y1 y. G% i但是，上面的思考过程还是最根本的。所以问题变为两个：知道前j个元素的next的情况下，
+ _" L* `7 c+ ~$ g& o①next[j+1]的可能的最大值是多少（即从哪开始验证）
! O0 X# o' d" ^5 K# V+ J②某一步验证失败后，需要“前去尾几个，后掐头几个？”（即本次验证失败后，再验证哪个值）
( u) N- z2 N8 q' d' G看一下的分析：

7 x2 _) \% N/ x
: r2 v: q9 [+ C1、next[j+1]的最大值为next[j]+1。
2 f8 ~! V) A' ]1 f7 F; ^因为：
% U1 p. W$ s4 G. l; m; F假设next[j]=k1，则可以说明P1…Pk1-1=Pj-k1+1…Pj-1，且这是前j个元素最大的首尾重合序列。
' R% {, R* R7 ]- N% g7 y  ?如果Pk1=Pj，那么P1…Pk1-1PK=Pj-k1+1…Pj-1Pj，那么k+1这也是前j+1个元素的最大首尾重合序列，也即next[j+1]的值为k1+1
: W) l8 X" s% L( b% [" x/ @2、如果Pk1≠Pj，那么next[j+1]可能的次大值为next[next[j]]+1，以此类推即可高效求出next[j+1]
4 w4 R" Y$ ~  J6 ?; t# ]这里不好解释，直接看下面的流程分析及图解
0 A, o% {* n, A& ^* U' ^& r& O3 @4 O
( U5 o4 z# W7 t8 s
开——始——划——重——点！
从头走一遍流程
①求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
⑤第二第三步联合得到:
- H6 j3 Z" |+ c( x- b& s  TP1…Pk2-1 = Pk1-k2+1…Pk1-1 = Pj-k1+1…Pk2-k1+j-1 = Pj-k2+1…Pj-1 即四段重合
⑥这时候，再判断如果Pk2=Pj，则P1…Pk2-1P~k2 = Pj-k2+1…Pj-1Pj，则next[j+1]=k2+1；否则再取next[k2]=k3…以此类推
1 z2 x$ O5 v6 Z( Y* R6 k- J! ]
/ i- n2 m# C# n6 w# l- j& O/ P
上面几步，耐心看下来，结合那个式子很容易看懂。最后，再加一个图的模拟帮助理解：
1、要求next[k+1] 其中k+1=17
2 c5 S+ Y& T( T; q

2、已知next[16]=8，则元素有以下关系：
: |& X+ S7 S3 V3 o, F+ A# d

1 l; u7 c2 R: C$ @$ y% m$ k3、如果P8=P16，则明显next[17]=8+1=9
2 s) l: \; }, y6 D' @/ p7 ]4、如果不相等，又若next[8]=4，则有以下关系
* N' V# E. x7 X% E+ k  e
1 w: z$ L+ i7 l
; Y- i& @4 E( q( S# d1 X2 {又加上2的条件知

6 m; O& T6 m5 t- ^% Y) v
1 u& F: `$ ^2 `1 _' H( z& q主要是为了证明：


5、现在在判断，如果P16=P4则next[17]=4+1=5，否则，在继续递推
5 `* |2 I( Q% B! Z3 a6、若next[4]=2，则有以下关系


) ^) M5 A1 x; o4 N5 @7、若P16=P2，则next[17]=2+1=3;否则继续取next[2]=1、next[1]=0；遇到0时还没出结果，则递推结束，此时next[17]=1。最后，再返回看那5行算法，应该很容易明白了！
: }" w& ~' M. ?8 X" v7 I————————————————
版权声明：本文为CSDN博主「Sirm23333」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_37969433/article/details/82947411
" t$ m- B" f" M& q# ~: }) t6 H0 M
. [6 ^; p1 Z' P, n3 h