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

杨利霞

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

6 M% P+ S( }( U1 i- t大多数据结构课本中，串涉及的内容即串的模式匹配，需要掌握的是朴素算法、KMP算法及next值的求法。在考研备考中，参考严奶奶的教材，我也是在关于求next值的算法中卡了一下午时间，感觉挺有意思的，把一些思考的结果整理出来，与大家一起探讨。

2 R8 c7 `* U1 ^3 y; Z9 D" K4 ?- ^' P
6 n0 g( X1 |/ G7 r/ B  u本文的逻辑顺序为
1、最基本的朴素算法
# u0 A" |; L4 M8 ~  K3 P7 x2、优化的KMP算法
3、应算法需要定义的next值
4、手动写出较短串的next值的方法
( ^! h2 M8 L1 @# d5、最难理解的、足足有5行的代码的求next值的算法
所有铺垫为了最后的第5点，我觉得以这个逻辑下来，由果索因还是相对好理解的，下面写的很通俗，略显不专业…
  V" T% b  n" p
# z! M5 z+ z; C9 t- H2 a* {
一、问题描述
给定一个主串S及一个模式串P，判断模式串是否为主串的子串；若是，返回匹配的第一个元素的位置（序号从1开始），否则返回0；如S=“abcd”，P=“bcd”，则返回2；S=“abcd”，P=“acb”，返回0。
, p- L# ~: B  V0 ~5 K3 Z6 v
+ C7 o3 T4 P& C: B. S
二、朴素算法
# r5 h( B% p& M2 Y6 Y6 j最简单的方法及一次遍历S与P。以S=“abcabaaaabaaacac”,P="abaabcac"为例，一张动图模拟朴素算法：



4 x4 Z% p& i: A) F
这个算法简单，不多说，附上代码


#include<stdio.h>
. Y/ c+ _; L0 w# H" `+ Kint Index_1(char s[],int sLen,char p[],int pLen){//s为主串，sLen为主串元素个数，p为模式串，pLen为模式串的个数
" Q1 ]% y% u) o) j2 c6 Y    if(sLen<pLen)return 0;
    int i = 1,j = 1;
    while(i<=sLen && j<=pLen){
1 M7 R) b' K4 j; K  I8 C        if(s==p[j]){i++;j++;}
, ?$ a( O* \0 Q! e        else{
# q  h$ |6 N) d# W. ?5 T            i = i-j+2;
& d) c& y' I/ r- x6 S            j = 1;
, W9 k( ?8 p# a( u        }
    }
% K  n6 i- d3 x& ~6 \; E    if(j>pLen) return i-pLen;
    return 0;
1 \4 ]7 e  ]! p}
4 b) q6 l8 P9 svoid 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'};
: e/ p) t0 u! s3 G! k$ F    int sLen = sizeof(s)/sizeof(char)-1;
    int pLen = sizeof(p)/sizeof(char)-1;
* e- V% s% S2 n2 F" x* ~    printf("%d",Index_1(s,sLen,p,pLen));
}
: z0 U; o: T2 K% ]1
1 V5 J) [- l# S7 e2
3
! D9 b# ^7 ^9 J4 ]2 I8 ~4
5
6
7
. i% r1 I. J8 X0 `8
) ^9 a/ R! S# W5 o9
10
11
12
13
- R5 B( R; C3 h+ Z4 j14
15
9 \+ U  E: L4 ~6 G3 C. h7 @2 r16
17
9 B5 r6 \. f. ~! s* d18
19
4 j6 O% T) k' X+ ^" ~' |20
21
1 Z/ L; A% R' S+ ~: u$ L三、改进的算法——KMP算法
. J! F% t% l+ h朴素算法理解简单，但两个串都有依次遍历，时间复杂度为O(n*m)，效率不高。由此有了KMP算法。
一般的，在一次匹配中，我们是不知道主串的内容的，而模式串是我们自己定义的。
- K  }. Q, G9 f4 X' f% d2 ^( }! p朴素算法中，P的第j位失配，默认的把P串后移一位。
, F; P" X+ W' n( E( x但在前一轮的比较中，我们已经知道了P的前(j-1)位与S中间对应的某(j-1)个元素已经匹配成功了。这就意味着，在一轮的尝试匹配中，我们get到了主串的部分内容，我们能否利用这些内容，让P多移几位(我认为这就是KMP算法最根本的东西)，减少遍历的趟数呢？答案是肯定的。再看下面改进后的动图：
3 f0 Y- i, d5 l$ ~7 u
  {* l) k7 q: [# v  M% ^# I' H

5 @- _& Q$ a/ G! G( r2 p
这个模拟过程即KMP算法，若没有看明白，继续往下看相应的解释，理解需要把P多移几位，然后回头再看一遍这个图就很明了了。
% M7 p- w  X' R' B$ z+ Q8 ]
* j- y/ w5 c3 h- A% C
" t1 c$ n2 Y9 W5 p相比朴素算法：
! _/ \" w* ?  b& G* K9 b朴素算法： 每次失配，S串的索引i定位的本次尝试匹配的第一个字符的后一个。P串的索引j定位到1；T(n)=O(n*m)
4 G! H- w: l$ u' K$ i! }KMP算法： 每次失配，S串的索引i不动，P串的索引j定位到某个数。T(n)=O(n+m)，时间效率明显提高


而这“定位到某个数”，这个数就是接下来引入的next值。（实际上也就是P往后移多少位，换一种说法罢了：从上图中也可以看出，失配时固定i不变，令S与P[某个数]对齐，实际上是P右移几位的另一种表达，只有为什么这么表达，当然是因为程序好写。）

) \2 F% i5 J# @$ h' c
开——始——划——重——点！（图对逻辑关系比较好理解，但i和j的关系对后面求next的算法好理解！）
; h5 g6 a& L& i0 H2 f

% C0 ?7 v! i3 S! d9 Q. \比如，Pj处失配，绿色的是Pj，则我们可以确定P1…Pj-1是与Si…Si+j-2相对应的位置一一相等的


  r" b$ b) P; N
假设P1…Pj-1中，P1…Pk-1与Pj-k+1…Pj-1是一一相等的，为了下面说的清楚，我们把这种关系叫做“首尾重合”
2 n. Z/ B! g8 x+ M" Q0 [) V, }3 V



那么可以推出，P1…Pk-1与Si…Si+j-2
/ B% h; @$ P: _, F/ G( ~  i  E



1 X; u# P: [; M. c9 h/ Y3 Z. m显然，接下来要做的就是把模式串右移了，移到哪里就不用多说了：
9 \9 t4 V8 L% Q; X


5 ~- P! ^6 x; R5 d0 n8 [! Q6 i. ~' I
为了表示下一轮比较j定位的地方，我们将其定义为next[j]，next[j]就是第j个元素前j-1个元素首尾重合部分个数加一，当然，为了能遍历完整，首尾重合部分的元素个数应取到最多，即next[j]应取尽量大的值，原因挺好理解的，可以想个例子模拟一下，会完美跳过正确结果。在上图中就是绿色元素的next值为蓝色元素的序号。也即，对于字符串P，next[8]=4。如此，再看一下上面的动图是不是清楚了不少。
0 |- o( a( a+ T. ~3 q
5 y; h1 o- j4 x9 ]+ U! N4 \
5 ^* @) u$ ~6 r2 U最后，如果我们知道了一个字符串的next值，那么KMP算法也就很好懂了。相比朴素算法，当发生失配时，i不变，j=next[j]就好啦！接下来就是怎么确定next值了。
( Y6 H( g. d& o: p' H

四、手动写出一个串的next值
1 A8 ^- d7 Q+ E4 @我们规定任何一个串，next[1]=0。(不用next[0]，与串的所有对应)，仍是一张动图搞定问题：
8 N  [0 i/ U- t9 Q
$ m" b9 P  }0 l) y# _
! p& I% J0 E) B' F- {4 U  I( Z# C) M, M这个扫一眼就能依次写出，会了这个方法，应付个期末考试没问题了。


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



# q; Z3 t# d1 g% S) n! R
/ I' B. e8 J6 C! w五、求next的算法
; O8 Y  [6 W; J( G终于到了最后了~短的串的next值我们可以“看”出来，但长的串就需要借助程序了，具体算法刚接触的时候确实不容易理解，但给我的体验，把上面的内容写完，现在感觉简简单单了…先附上程序再做解释，(终于到了传说中的整整5行代码让我整理了一下午)。
& p, N' P0 H2 Z4 e& V9 Q

4 T) i0 y9 z+ W( Jint GetNext(char ch[],int cLen,int next[]){//cLen为串ch的长度
    next[1] = 0;
2 i! Q9 t, C8 E0 I$ f    int i = 1,j = 0;
    while(i<=cLen){
: ]; {7 P2 ^* a: x) `        if(j==0||ch==ch[j]) next[++i] = ++j;
% W) \: O# N; p0 g# x% c        else j = next[j];
    }
0 g. F2 s" ^8 W2 }, `: K: D}
* a# M2 Z( j, p* D' Z& V& E
; ~5 ]' S/ {# g. j% t还是先由一般再推优化：
, C* u( v& n2 e" l9 o直接求next[j+1]（至于为什么是j+1，是为了和下面的对应）
根据之前的分析，next[j+1]的值为pj+1的前j个元素的收尾重合的最大个数加一。即需要满足两个条件，把它的值一步步“检验”出来。一是“个数最多”的，因此要从可能的最大值开始验；二是“首尾重合”，因此要一一对应验是否相等。
不难理解，next[j+1]的最大值为j，所有我们从next[j+1]=j开始“验证”。有以下优先判断顺序：
; v# M' P. V3 o& N7 Lif(P1…Pj-1 == P2…Pj) => next[j+1]=j
else if(P1…Pj-2 == P3…Pj) =>next[j+1]=j-1
( Y, j! X4 @- d0 ^- F2 H: relse if(P1…Pj-3 == P4…Pj) =>next[j+1]=j-2
…
1 @% t1 F- A+ A9 n6 g4 k…
% s9 k& _; U$ X5 {- M# [' r9 T2 D…
% {; J) C% }* B! Yelse if(P1P2 == Pj-1Pj) => next[j+1]=3
else if(P1 == Pj-1) => next[j+1]=2
1 C7 \  s, o, T8 zelse if(P1 != Pj-1) => next[j+1]=1
4 E% }6 |6 w6 m) a每次前去尾1个，后掐头1个，直至得到next[j+1]
0 v7 T" D4 ^6 n) q

再进一步想，next值是一个“工具”，我们单独的求next[j+1]是完全没有意义的，就是说要求next就要把所有j的next求出来。所有一般的，我们都是已知前j个元素的next值，求next[j+1]，以此递推下去，求完整的next数组。
4 W& v7 `" ?) H0 J: ?但是，上面的思考过程还是最根本的。所以问题变为两个：知道前j个元素的next的情况下，
①next[j+1]的可能的最大值是多少（即从哪开始验证）
3 D$ ^- ?5 c+ N* }7 N②某一步验证失败后，需要“前去尾几个，后掐头几个？”（即本次验证失败后，再验证哪个值）
3 b% ?, \( O8 y. F看一下的分析：


1、next[j+1]的最大值为next[j]+1。
* p5 q8 U! m# i, \% g因为：
假设next[j]=k1，则可以说明P1…Pk1-1=Pj-k1+1…Pj-1，且这是前j个元素最大的首尾重合序列。
2 G* @4 F5 S- n& q" e# J如果Pk1=Pj，那么P1…Pk1-1PK=Pj-k1+1…Pj-1Pj，那么k+1这也是前j+1个元素的最大首尾重合序列，也即next[j+1]的值为k1+1
% G# x0 ^% E, y5 m2 e1 `8 P  n2、如果Pk1≠Pj，那么next[j+1]可能的次大值为next[next[j]]+1，以此类推即可高效求出next[j+1]
这里不好解释，直接看下面的流程分析及图解


, S, O" d- s, F# [开——始——划——重——点！
" q5 X$ ~7 T$ q4 F; c: }6 ^8 t从头走一遍流程
①求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
. T  g" _8 a/ z6 i⑤第二第三步联合得到:
2 ~. r+ }" X! W+ nP1…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…以此类推

: `! r! }& B5 |# {; c* w) _
9 I& j2 H3 d' e6 b  N2 h上面几步，耐心看下来，结合那个式子很容易看懂。最后，再加一个图的模拟帮助理解：
% J4 ^) i' J7 {" |0 ?0 J1、要求next[k+1] 其中k+1=17
" W; H4 ]% X- A! i9 C5 }
9 x# F, ^# z; _) \& W9 V" X. m
7 l9 }* s' t. H2、已知next[16]=8，则元素有以下关系：

4 V$ D5 z" l! y0 {) H- z' X% @
9 x& F5 D- P; t2 ^. F3、如果P8=P16，则明显next[17]=8+1=9
4、如果不相等，又若next[8]=4，则有以下关系
3 P7 f$ T% l% Q1 N
* |. a8 P6 p9 u3 V
. ~9 r) F) @! W& W3 G  m又加上2的条件知

2 K4 R" n! F" ~1 N8 P$ a  N
主要是为了证明：
- D7 w7 M' l3 V; p0 ^3 e

5、现在在判断，如果P16=P4则next[17]=4+1=5，否则，在继续递推
6、若next[4]=2，则有以下关系
' E, w, C+ U# C+ x( \: Z5 D1 W. Q

7、若P16=P2，则next[17]=2+1=3;否则继续取next[2]=1、next[1]=0；遇到0时还没出结果，则递推结束，此时next[17]=1。最后，再返回看那5行算法，应该很容易明白了！
1 I5 W1 c6 E: a& Y8 s" K————————————————
版权声明：本文为CSDN博主「Sirm23333」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_37969433/article/details/82947411

) ]9 D- I0 h! z. a# c, D, o4 \
0 D* [1 ~# u' J) c' o+ u
9 U, M1 R( @0 ?