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

杨利霞

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

大多数据结构课本中，串涉及的内容即串的模式匹配，需要掌握的是朴素算法、KMP算法及next值的求法。在考研备考中，参考严奶奶的教材，我也是在关于求next值的算法中卡了一下午时间，感觉挺有意思的，把一些思考的结果整理出来，与大家一起探讨。
0 |! T9 L1 p' Y  V) _
6 ~; r8 A# }* Y- j0 p
' [! S) b( u& H/ l本文的逻辑顺序为
1、最基本的朴素算法
# R3 c+ _0 M  k- g0 L+ ~) W- U2、优化的KMP算法
3、应算法需要定义的next值
4、手动写出较短串的next值的方法
5、最难理解的、足足有5行的代码的求next值的算法
( w* }8 Y; e1 T9 \' V* ?, F4 h所有铺垫为了最后的第5点，我觉得以这个逻辑下来，由果索因还是相对好理解的，下面写的很通俗，略显不专业…
& |9 u3 X2 Y$ ]; {9 E
$ j( U$ O2 X1 E7 j
一、问题描述
给定一个主串S及一个模式串P，判断模式串是否为主串的子串；若是，返回匹配的第一个元素的位置（序号从1开始），否则返回0；如S=“abcd”，P=“bcd”，则返回2；S=“abcd”，P=“acb”，返回0。


二、朴素算法
最简单的方法及一次遍历S与P。以S=“abcabaaaabaaacac”,P="abaabcac"为例，一张动图模拟朴素算法：
- b# c0 u4 o; K: G$ E- o. ~, y) m

0 V( Q9 S4 ], [) h& B. U
/ y2 ^& M7 g# W3 n
这个算法简单，不多说，附上代码
2 j! o, e' u3 L5 H/ a1 R/ `% P
' k8 t  Q4 d2 N2 x( I) |
; A3 S, l2 [4 W#include<stdio.h>
int Index_1(char s[],int sLen,char p[],int pLen){//s为主串，sLen为主串元素个数，p为模式串，pLen为模式串的个数
    if(sLen<pLen)return 0;
    int i = 1,j = 1;
    while(i<=sLen && j<=pLen){
) |/ d9 q0 W% _& L9 a( }" ?        if(s==p[j]){i++;j++;}
        else{
) b4 g$ R! W" A# i7 p            i = i-j+2;
: `5 r5 V& q, ^) s            j = 1;
: r, a  p1 B9 X9 i" y! k! J. E3 V( T9 C        }
    }
5 j6 ^$ M% a6 ^7 _8 Q    if(j>pLen) return i-pLen;
9 y. ~) j! H, F. H: V    return 0;
* W' J! s8 m- _4 b. x0 B}
- S( J1 v/ n# E2 [/ C6 K6 ?$ Svoid main(){
0 l' g. I2 y5 b: w, |" x1 U    char s[]={' ','a','b','c','a','b','a','a','a','a','b','a','a','b','c','a','c'};//从序号1开始存
- g" c- u# D" i, K' q9 g    char p[]={' ','a','b','a','a','b','c','a','c'};
    int sLen = sizeof(s)/sizeof(char)-1;
1 `& y: s, ]& k4 {* n4 c    int pLen = sizeof(p)/sizeof(char)-1;
! q+ K- L$ ^7 Y    printf("%d",Index_1(s,sLen,p,pLen));
}
7 i$ H+ ?7 t5 m5 T* D1
2
. R; `" |# ^, X. V8 X3
4
5
$ D; m! [! C5 ]+ B9 u( S! r6
7
8
, m& Y! y3 G5 ?9
10
9 A; ~6 I2 j/ g' X) s11
12
/ ^0 D6 o" O6 Q8 C2 v7 }13
- l: k3 U$ N8 d; x+ W3 t: l0 |$ D14
) o/ N' l" X* e8 k, \, X4 n* [15
16
17
18
: o% Q- q8 @# _2 ~: U19
) D% Z& h" h+ l: D. H9 [2 S+ @2 x20
4 F& \( N6 P- C% [21
三、改进的算法——KMP算法
0 a0 {6 S" g+ o: t! x朴素算法理解简单，但两个串都有依次遍历，时间复杂度为O(n*m)，效率不高。由此有了KMP算法。
% J2 ?+ ~! w+ K* F一般的，在一次匹配中，我们是不知道主串的内容的，而模式串是我们自己定义的。
朴素算法中，P的第j位失配，默认的把P串后移一位。
7 f! d1 K. ?  C: r: z, y: }但在前一轮的比较中，我们已经知道了P的前(j-1)位与S中间对应的某(j-1)个元素已经匹配成功了。这就意味着，在一轮的尝试匹配中，我们get到了主串的部分内容，我们能否利用这些内容，让P多移几位(我认为这就是KMP算法最根本的东西)，减少遍历的趟数呢？答案是肯定的。再看下面改进后的动图：
* u# Z( z, [) }# T. A' G7 D

% {9 D: |, o! q0 z, C

这个模拟过程即KMP算法，若没有看明白，继续往下看相应的解释，理解需要把P多移几位，然后回头再看一遍这个图就很明了了。
6 O5 B! M) ?, M/ H' ], Y
$ T( U4 v# C+ }  [  \8 [0 b
  r( O/ m' z& s相比朴素算法：
- K+ g8 Q3 j, p  L$ t朴素算法： 每次失配，S串的索引i定位的本次尝试匹配的第一个字符的后一个。P串的索引j定位到1；T(n)=O(n*m)
$ q9 A/ h! D* |. |* k: n' [KMP算法： 每次失配，S串的索引i不动，P串的索引j定位到某个数。T(n)=O(n+m)，时间效率明显提高
9 y4 i; s1 O9 N8 W% b4 h
* }; O9 F5 {' @: Y! u
而这“定位到某个数”，这个数就是接下来引入的next值。（实际上也就是P往后移多少位，换一种说法罢了：从上图中也可以看出，失配时固定i不变，令S与P[某个数]对齐，实际上是P右移几位的另一种表达，只有为什么这么表达，当然是因为程序好写。）
2 m$ s+ a( S" w7 T
+ j0 t# z9 [" s
) g5 T' Q2 x5 d- v( V/ q开——始——划——重——点！（图对逻辑关系比较好理解，但i和j的关系对后面求next的算法好理解！）

4 u: t, G: m3 |, S
比如，Pj处失配，绿色的是Pj，则我们可以确定P1…Pj-1是与Si…Si+j-2相对应的位置一一相等的
8 v( [& P8 b2 N* e7 i( g# U

" r. A7 a" @# k3 z7 t0 p
1 o9 Y* M9 |+ Q$ f假设P1…Pj-1中，P1…Pk-1与Pj-k+1…Pj-1是一一相等的，为了下面说的清楚，我们把这种关系叫做“首尾重合”
) Y; ^% {& N' A

8 v- x+ m# W: _5 W  j
* T; t3 M9 m( F3 _) P  t4 X
那么可以推出，P1…Pk-1与Si…Si+j-2

" H# J* N6 x/ |( R. Y1 m) S* F
- P, u$ T4 }' j. b7 o

. v1 |) J, u* Y8 U1 V" J9 L显然，接下来要做的就是把模式串右移了，移到哪里就不用多说了：

5 l4 a+ Y/ h2 |9 {" H7 r$ ]3 [  }
( P6 ?$ F3 j# v/ M. q0 r
( W1 x% N8 K3 s
为了表示下一轮比较j定位的地方，我们将其定义为next[j]，next[j]就是第j个元素前j-1个元素首尾重合部分个数加一，当然，为了能遍历完整，首尾重合部分的元素个数应取到最多，即next[j]应取尽量大的值，原因挺好理解的，可以想个例子模拟一下，会完美跳过正确结果。在上图中就是绿色元素的next值为蓝色元素的序号。也即，对于字符串P，next[8]=4。如此，再看一下上面的动图是不是清楚了不少。

* \- c* _8 [7 F2 E
. i& t! A. j5 m9 j1 K; g# T最后，如果我们知道了一个字符串的next值，那么KMP算法也就很好懂了。相比朴素算法，当发生失配时，i不变，j=next[j]就好啦！接下来就是怎么确定next值了。
2 ]9 ~( C3 a/ g( i

四、手动写出一个串的next值
3 N, O8 b1 {$ A! U. ?. I6 g我们规定任何一个串，next[1]=0。(不用next[0]，与串的所有对应)，仍是一张动图搞定问题：
/ P/ ^! W- b1 K
+ `0 U* B2 Q6 V+ S
这个扫一眼就能依次写出，会了这个方法，应付个期末考试没问题了。
: X6 [* @$ d9 e9 q0 D1 b( w# [

通过把next值“看”出来，我们再来分析next值，这就很容易得到超级有名的公式了，这个式子对后面的算法理解很重要！所以先要看懂这个式子，如果上面的内容通下来了，这个应该很容易看懂了：


1 z( P; E' x0 i& Y. `
: E2 \. S9 \) F2 Z/ X
- Q% n" _; e( D" {( b五、求next的算法
1 E4 H6 S3 H7 g* E# w2 n, R终于到了最后了~短的串的next值我们可以“看”出来，但长的串就需要借助程序了，具体算法刚接触的时候确实不容易理解，但给我的体验，把上面的内容写完，现在感觉简简单单了…先附上程序再做解释，(终于到了传说中的整整5行代码让我整理了一下午)。


3 m: s( b2 ^* H+ zint GetNext(char ch[],int cLen,int next[]){//cLen为串ch的长度
    next[1] = 0;
    int i = 1,j = 0;
! u0 W2 h, k! A* R1 `! y( [    while(i<=cLen){
        if(j==0||ch==ch[j]) next[++i] = ++j;
        else j = next[j];
    }
}

还是先由一般再推优化：
直接求next[j+1]（至于为什么是j+1，是为了和下面的对应）
. r5 t- F) [0 }* ^3 N% _% G根据之前的分析，next[j+1]的值为pj+1的前j个元素的收尾重合的最大个数加一。即需要满足两个条件，把它的值一步步“检验”出来。一是“个数最多”的，因此要从可能的最大值开始验；二是“首尾重合”，因此要一一对应验是否相等。
不难理解，next[j+1]的最大值为j，所有我们从next[j+1]=j开始“验证”。有以下优先判断顺序：
# e6 }) r5 w% A  e9 Wif(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
…
9 W1 J" [/ ?& R2 J% `" `…
$ N& L& e/ U; y…
+ k, _. x) d: n* V$ V; ?' ^else if(P1P2 == Pj-1Pj) => next[j+1]=3
else if(P1 == Pj-1) => next[j+1]=2
+ N0 d: L  v: q  r! i: Helse if(P1 != Pj-1) => next[j+1]=1
每次前去尾1个，后掐头1个，直至得到next[j+1]
! z+ u  n2 Q0 y

+ E8 Q1 h+ d( m0 ?% G" N再进一步想，next值是一个“工具”，我们单独的求next[j+1]是完全没有意义的，就是说要求next就要把所有j的next求出来。所有一般的，我们都是已知前j个元素的next值，求next[j+1]，以此递推下去，求完整的next数组。
! d7 g0 H! ?6 a$ O) v) F8 P" k但是，上面的思考过程还是最根本的。所以问题变为两个：知道前j个元素的next的情况下，
3 a* o6 k+ o5 `% g: Z4 A①next[j+1]的可能的最大值是多少（即从哪开始验证）
②某一步验证失败后，需要“前去尾几个，后掐头几个？”（即本次验证失败后，再验证哪个值）
看一下的分析：

2 F' H& K6 S$ o+ ]7 Z
1 G% v" v- H0 p* A' X1、next[j+1]的最大值为next[j]+1。
* Y! ]  B0 H, d- t& u4 }因为：
假设next[j]=k1，则可以说明P1…Pk1-1=Pj-k1+1…Pj-1，且这是前j个元素最大的首尾重合序列。
  s" O- I: `" w! w) b如果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]
这里不好解释，直接看下面的流程分析及图解

# t  ?! G5 P; n* x
$ v* u# B8 m6 f1 G0 I% h1 B4 {# w8 t开——始——划——重——点！
从头走一遍流程
/ c) {! [& Q, b6 }6 n" U# P6 i: }①求next[j+1]，设值为m
②已知next[j]=k1，则有P1…Pk1-1 = Pj-k1+1…Pj-1
, b/ u  A* f3 @* Y( x# Q, O③如果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 即四段重合
& g7 S6 \+ y  L* U⑥这时候，再判断如果Pk2=Pj，则P1…Pk2-1P~k2 = Pj-k2+1…Pj-1Pj，则next[j+1]=k2+1；否则再取next[k2]=k3…以此类推
+ Z0 o+ G- X7 N# p3 K- L: W

: }. ~. w( ?6 v5 W上面几步，耐心看下来，结合那个式子很容易看懂。最后，再加一个图的模拟帮助理解：
1、要求next[k+1] 其中k+1=17


7 S; c( y3 U/ _* J) r' s1 [  r' x( U/ R2、已知next[16]=8，则元素有以下关系：
: Q: ^5 L, X( ]

6 A, H- T' o5 f( V3、如果P8=P16，则明显next[17]=8+1=9
4、如果不相等，又若next[8]=4，则有以下关系
; q* s4 M0 m% u  U5 H  L# y

# N4 p4 [, Q: u) Y/ e- H又加上2的条件知


! ~, ~0 F/ h1 [) H6 ~4 c' r主要是为了证明：
9 ]) O6 E) u) @5 N+ m0 g3 d$ \
& W. [6 o* z% L  S) R6 Z& }
, F$ A% T1 e' N: W4 v: P* [5、现在在判断，如果P16=P4则next[17]=4+1=5，否则，在继续递推
6、若next[4]=2，则有以下关系
) H* ^$ T) k6 E8 S, B
: c6 y) A! \; v9 ]0 \
- H. d2 u- z7 a; }/ V7、若P16=P2，则next[17]=2+1=3;否则继续取next[2]=1、next[1]=0；遇到0时还没出结果，则递推结束，此时next[17]=1。最后，再返回看那5行算法，应该很容易明白了！
5 p. @: r9 k( B0 k4 s————————————————
. v! I( H+ r" i- W版权声明：本文为CSDN博主「Sirm23333」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_37969433/article/details/82947411
$ n" k% z: x* Z- q7 ]