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

杨利霞

（算法）通俗易懂的字符串匹配KMP算法及求next值算法
- n# ~# x; Q6 U( e" P
" ?3 R+ @( r0 m9 V: G大多数据结构课本中，串涉及的内容即串的模式匹配，需要掌握的是朴素算法、KMP算法及next值的求法。在考研备考中，参考严奶奶的教材，我也是在关于求next值的算法中卡了一下午时间，感觉挺有意思的，把一些思考的结果整理出来，与大家一起探讨。
! s' c& y3 T9 X- U1 {9 ]

本文的逻辑顺序为
1、最基本的朴素算法
2、优化的KMP算法
3、应算法需要定义的next值
/ I# F1 m$ N- X1 z/ u; ^4、手动写出较短串的next值的方法
4 N8 _* g" z! l, N2 J7 g5、最难理解的、足足有5行的代码的求next值的算法
所有铺垫为了最后的第5点，我觉得以这个逻辑下来，由果索因还是相对好理解的，下面写的很通俗，略显不专业…
( b. e1 h4 D" o5 \
$ }/ M7 b. R* t) X8 j
; k! B; [8 {9 U2 }+ y' v一、问题描述
给定一个主串S及一个模式串P，判断模式串是否为主串的子串；若是，返回匹配的第一个元素的位置（序号从1开始），否则返回0；如S=“abcd”，P=“bcd”，则返回2；S=“abcd”，P=“acb”，返回0。
, d; q- `' Y5 b, m, N7 e
4 z! ^/ c7 b6 M' @  R! J5 s. z
, @6 Q5 v6 g' A, p. \二、朴素算法
最简单的方法及一次遍历S与P。以S=“abcabaaaabaaacac”,P="abaabcac"为例，一张动图模拟朴素算法：
( A$ }* ^9 B$ t) ~' S1 ?- q3 h
6 U7 L( h  X) Y* ]+ Z3 L4 ]1 x


这个算法简单，不多说，附上代码

- ^2 D3 J: m( i( z3 k
# w2 B* x0 ?% Z$ |8 c# C: J9 L#include<stdio.h>
int Index_1(char s[],int sLen,char p[],int pLen){//s为主串，sLen为主串元素个数，p为模式串，pLen为模式串的个数
( w: d& @) l' b8 @    if(sLen<pLen)return 0;
! X. a7 q- u! E1 k3 Z4 {. U    int i = 1,j = 1;
    while(i<=sLen && j<=pLen){
        if(s==p[j]){i++;j++;}
" t9 Q* M& ^' J( x: n- ~* i        else{
            i = i-j+2;
            j = 1;
9 j6 [0 B3 w$ g' ]$ D. G1 b        }
+ L9 P; _$ @0 k3 l9 i8 i7 ]4 @1 J    }
    if(j>pLen) return i-pLen;
; M& U7 P' B+ h6 n; N    return 0;
: g% C" k4 t. t5 m}
- {$ [9 K4 Y- K, ~" e- c; lvoid main(){
% n' k, o2 `/ c0 Q    char s[]={' ','a','b','c','a','b','a','a','a','a','b','a','a','b','c','a','c'};//从序号1开始存
+ ^* I$ ]8 ~5 B: Q    char p[]={' ','a','b','a','a','b','c','a','c'};
/ z5 M9 h) f% r- ]    int sLen = sizeof(s)/sizeof(char)-1;
1 G: a- e9 t) d  u9 d3 `    int pLen = sizeof(p)/sizeof(char)-1;
    printf("%d",Index_1(s,sLen,p,pLen));
. o- W  q2 h9 k3 ~/ j}
8 p, U+ Z* q' u1 {1
2
3
' h; O, C( C3 S4
5
6
% c/ f8 H2 g3 {7
8
9
10
6 M* ~' b0 E8 H11
* O4 c( t4 Y: }6 u; q/ s# ^7 n12
+ y; @2 N  o) J6 m  [5 h9 k13
6 O# r5 e! [8 S" [  b14
9 V% Q# D# ?% U, B$ i1 s% a15
7 J) x0 m3 y# ~* D  W16
17
0 K% T- N4 j7 r2 L8 L: R% ~% M9 c18
19
* g6 t. w) I& f' r4 W/ X20
3 c* [7 B. Y& @21
$ s& {& \# Z4 d9 Y三、改进的算法——KMP算法
朴素算法理解简单，但两个串都有依次遍历，时间复杂度为O(n*m)，效率不高。由此有了KMP算法。
一般的，在一次匹配中，我们是不知道主串的内容的，而模式串是我们自己定义的。
" u8 P6 m% j) V7 Y. D" S朴素算法中，P的第j位失配，默认的把P串后移一位。
但在前一轮的比较中，我们已经知道了P的前(j-1)位与S中间对应的某(j-1)个元素已经匹配成功了。这就意味着，在一轮的尝试匹配中，我们get到了主串的部分内容，我们能否利用这些内容，让P多移几位(我认为这就是KMP算法最根本的东西)，减少遍历的趟数呢？答案是肯定的。再看下面改进后的动图：




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

4 g" x8 ]8 D/ p( m% X! o, J8 q
- p0 O3 K  m. a相比朴素算法：
& ^; w# g: C5 W/ ^* D: A朴素算法： 每次失配，S串的索引i定位的本次尝试匹配的第一个字符的后一个。P串的索引j定位到1；T(n)=O(n*m)
* h6 T1 F1 h, @% O# ^4 ?KMP算法： 每次失配，S串的索引i不动，P串的索引j定位到某个数。T(n)=O(n+m)，时间效率明显提高

9 W/ e5 U6 w; L4 @
0 h" o% E' X$ x  N" j: ?% {3 P+ r而这“定位到某个数”，这个数就是接下来引入的next值。（实际上也就是P往后移多少位，换一种说法罢了：从上图中也可以看出，失配时固定i不变，令S与P[某个数]对齐，实际上是P右移几位的另一种表达，只有为什么这么表达，当然是因为程序好写。）


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

! o& X, M; Z) V9 ~6 Y- y( b( @5 B. u
9 ]9 a2 j7 z- ]2 L" K比如，Pj处失配，绿色的是Pj，则我们可以确定P1…Pj-1是与Si…Si+j-2相对应的位置一一相等的
) s( t) P3 Q% x2 P. y. e
; H$ ~$ m: M* r  y

! S3 Y1 n8 m6 K, a5 s5 p' {( s假设P1…Pj-1中，P1…Pk-1与Pj-k+1…Pj-1是一一相等的，为了下面说的清楚，我们把这种关系叫做“首尾重合”
* K% ?& ]- s: j, f0 r) v2 v7 m4 E

$ B* `6 ], m, u. R
! i. z) T7 M/ T" E( X
那么可以推出，P1…Pk-1与Si…Si+j-2



- p# W0 w: v6 m: Q/ m
显然，接下来要做的就是把模式串右移了，移到哪里就不用多说了：
' @1 @: W- \+ ]. V


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

& r( P. Z4 ~9 o* ]) u5 w5 W+ l
最后，如果我们知道了一个字符串的next值，那么KMP算法也就很好懂了。相比朴素算法，当发生失配时，i不变，j=next[j]就好啦！接下来就是怎么确定next值了。

3 e( ~; L4 E7 d' ^
, H; v# e) r: m& h7 H四、手动写出一个串的next值
8 L! M& X7 e: S* K我们规定任何一个串，next[1]=0。(不用next[0]，与串的所有对应)，仍是一张动图搞定问题：

/ e* L: i4 E) \3 [% E* I& u; C% l
1 Z+ \5 s9 R: `' [9 n& q# I, I: H这个扫一眼就能依次写出，会了这个方法，应付个期末考试没问题了。
, `3 V% K' k) Q' J5 x: B
: u$ a5 A0 v% P
通过把next值“看”出来，我们再来分析next值，这就很容易得到超级有名的公式了，这个式子对后面的算法理解很重要！所以先要看懂这个式子，如果上面的内容通下来了，这个应该很容易看懂了：
6 @0 M9 K+ H% c" y0 [

0 \4 B( f: t0 |5 {) y

6 |& W& r" t9 w% [五、求next的算法
& c) t( T/ d! a1 J终于到了最后了~短的串的next值我们可以“看”出来，但长的串就需要借助程序了，具体算法刚接触的时候确实不容易理解，但给我的体验，把上面的内容写完，现在感觉简简单单了…先附上程序再做解释，(终于到了传说中的整整5行代码让我整理了一下午)。
/ X. J* T4 w* ]
8 K( ?8 u6 t! \8 K/ x  ^
7 j- H/ x" V0 R4 M; q2 q% @' r+ [int GetNext(char ch[],int cLen,int next[]){//cLen为串ch的长度
! c# a8 g7 |2 S& a% u% c    next[1] = 0;
, C& u* n( @1 C& y7 R* n    int i = 1,j = 0;
    while(i<=cLen){
6 b! K: r% c' V) J! ?, h0 U$ `- K        if(j==0||ch==ch[j]) next[++i] = ++j;
        else j = next[j];
/ b! f- W4 S8 J+ S  ^, m    }
% G$ o9 ]4 s* m) v6 l* n}
9 E/ e, _( \/ ]. J  m  n$ M
还是先由一般再推优化：
# m- d- ^, P) a8 H: o# I' w直接求next[j+1]（至于为什么是j+1，是为了和下面的对应）
  n' C  z) a" m) M  z0 K根据之前的分析，next[j+1]的值为pj+1的前j个元素的收尾重合的最大个数加一。即需要满足两个条件，把它的值一步步“检验”出来。一是“个数最多”的，因此要从可能的最大值开始验；二是“首尾重合”，因此要一一对应验是否相等。
不难理解，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
$ u9 c4 E! Y: t: j% m; d2 i…
…
…
6 H5 Q, q, c1 o+ P+ A) V* ]else if(P1P2 == Pj-1Pj) => next[j+1]=3
else if(P1 == Pj-1) => next[j+1]=2
2 X' ~' G* ^" x5 Felse if(P1 != Pj-1) => next[j+1]=1
& u. w+ m" c) [每次前去尾1个，后掐头1个，直至得到next[j+1]
5 ]# F6 e0 X6 N; ~( l& r

" H; A0 Z5 V% E/ v再进一步想，next值是一个“工具”，我们单独的求next[j+1]是完全没有意义的，就是说要求next就要把所有j的next求出来。所有一般的，我们都是已知前j个元素的next值，求next[j+1]，以此递推下去，求完整的next数组。
但是，上面的思考过程还是最根本的。所以问题变为两个：知道前j个元素的next的情况下，
①next[j+1]的可能的最大值是多少（即从哪开始验证）
②某一步验证失败后，需要“前去尾几个，后掐头几个？”（即本次验证失败后，再验证哪个值）
5 L' k& h% P$ n+ m& Y- V6 D+ |看一下的分析：


1、next[j+1]的最大值为next[j]+1。
因为：
3 p& i. X; c# r; h, E0 g7 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
8 f& d- u, R6 o$ f) Q4 {8 k, Z2、如果Pk1≠Pj，那么next[j+1]可能的次大值为next[next[j]]+1，以此类推即可高效求出next[j+1]
这里不好解释，直接看下面的流程分析及图解
9 n6 M# C; @- q& f* f2 n, c# L* x

开——始——划——重——点！
从头走一遍流程
①求next[j+1]，设值为m
" n; i- ~5 l2 G2 C+ g, h②已知next[j]=k1，则有P1…Pk1-1 = Pj-k1+1…Pj-1
) D) G1 H# ~' E+ }8 c0 H2 l# r③如果Pk1=Pj，则P1…Pk1-1PK = Pj-k1+1…Pj-1Pj，则next[j+1]=k1+1，否则
) X! b/ q6 u& [( c4 y$ _+ Q④已知next[k1]=k2，则有P1…Pk2-1 = Pk1-k2+1…Pk1-1
⑤第二第三步联合得到:
, _0 e- W* E) k# LP1…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…以此类推
* }5 O) P! g; l; W. `0 W1 K* K
9 R5 R  J5 }3 |
6 }6 {! I/ C/ Q9 D0 I" h9 h2 j+ p上面几步，耐心看下来，结合那个式子很容易看懂。最后，再加一个图的模拟帮助理解：
4 U& H  s6 ]: N6 T1、要求next[k+1] 其中k+1=17
  T# S5 Z0 v4 O- H/ z+ |& m
* H0 n# k2 z# `) i" o1 |' W, c
. N. B9 s2 l# K! b: R+ v0 Y2、已知next[16]=8，则元素有以下关系：
7 y9 E4 k: o# e6 n9 H- I
/ F) A' L: k, `$ `4 n1 i; t
6 w) h* I3 P2 I+ b( O3、如果P8=P16，则明显next[17]=8+1=9
4、如果不相等，又若next[8]=4，则有以下关系

/ M, J: D9 Q2 ]& x
又加上2的条件知


主要是为了证明：

6 U9 A/ J' j: ]: v1 h% B
1 M0 W6 ~6 a- w6 T1 M3 v5、现在在判断，如果P16=P4则next[17]=4+1=5，否则，在继续递推
0 G% H( l% \" I. i6、若next[4]=2，则有以下关系
; \  ]6 z3 W  t# M( d  E# v5 w
, S* G- V: `5 T, g6 Y6 [9 F+ P, t
% }# x# E  x. ^$ s' u7、若P16=P2，则next[17]=2+1=3;否则继续取next[2]=1、next[1]=0；遇到0时还没出结果，则递推结束，此时next[17]=1。最后，再返回看那5行算法，应该很容易明白了！
) I! G6 w) a, L: x# v————————————————
7 S" d' |5 a) ~/ a6 w* D6 f$ q版权声明：本文为CSDN博主「Sirm23333」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_37969433/article/details/82947411
. S- {2 X5 b$ _