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

杨利霞

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

# X) U& d" f' m8 ^( N大多数据结构课本中，串涉及的内容即串的模式匹配，需要掌握的是朴素算法、KMP算法及next值的求法。在考研备考中，参考严奶奶的教材，我也是在关于求next值的算法中卡了一下午时间，感觉挺有意思的，把一些思考的结果整理出来，与大家一起探讨。
1 ~6 L6 Z- _! F/ X( j  n7 J  [+ i
. }% o3 Z, [9 j0 |7 q3 v8 h
本文的逻辑顺序为
1、最基本的朴素算法
4 u* r  X9 V" \9 E4 i2、优化的KMP算法
' s$ p5 z* F. p% F3、应算法需要定义的next值
4、手动写出较短串的next值的方法
5、最难理解的、足足有5行的代码的求next值的算法
所有铺垫为了最后的第5点，我觉得以这个逻辑下来，由果索因还是相对好理解的，下面写的很通俗，略显不专业…
2 N$ c1 _: C* D9 O

  S& z' W& W: T一、问题描述
) [6 n0 i$ K5 X" k5 M, I. f给定一个主串S及一个模式串P，判断模式串是否为主串的子串；若是，返回匹配的第一个元素的位置（序号从1开始），否则返回0；如S=“abcd”，P=“bcd”，则返回2；S=“abcd”，P=“acb”，返回0。


二、朴素算法
, N0 n+ M  `% R, Z/ x, P最简单的方法及一次遍历S与P。以S=“abcabaaaabaaacac”,P="abaabcac"为例，一张动图模拟朴素算法：
, x/ f2 _6 _5 e1 j# [
% ]) @) h# Z4 l
/ H! \* ~( d; K$ s* N$ k/ x+ U; G
2 L, I+ |+ @. Y) n" B& B% Q1 m
这个算法简单，不多说，附上代码

; e9 q- v" m( z- Y" n: e- G
#include<stdio.h>
/ i# ^1 G( r! X# C( _int Index_1(char s[],int sLen,char p[],int pLen){//s为主串，sLen为主串元素个数，p为模式串，pLen为模式串的个数
6 e2 [3 f7 n, p/ K    if(sLen<pLen)return 0;
1 x, O4 W: h! J$ C( U, Y    int i = 1,j = 1;
8 L+ \. {. ]) c- M) N% y    while(i<=sLen && j<=pLen){
        if(s==p[j]){i++;j++;}
3 N- R: n/ X! p7 s        else{
! C: k9 T1 m, \, `            i = i-j+2;
! m9 ^& h6 q5 N            j = 1;
, G5 S- l3 m# |0 P        }
% J, V/ k. |+ R: ]7 y3 |) b5 I    }
$ F- c9 j: W  J( g: g    if(j>pLen) return i-pLen;
    return 0;
/ P4 B, G% c1 S% i/ d0 \7 Y6 v+ Q% ]}
void main(){
    char s[]={' ','a','b','c','a','b','a','a','a','a','b','a','a','b','c','a','c'};//从序号1开始存
& H7 h8 k- `* e+ S5 ]. i    char p[]={' ','a','b','a','a','b','c','a','c'};
    int sLen = sizeof(s)/sizeof(char)-1;
. C8 k4 W, A9 F4 ^9 Y1 ]* g    int pLen = sizeof(p)/sizeof(char)-1;
    printf("%d",Index_1(s,sLen,p,pLen));
) A  O, K4 }2 g}
1
2
/ R& Y4 t' ^# Q9 i. K3
4
* y+ {$ U! J  C" M5
6
7 _* B' A4 ?# R* X- W7
8 [; d9 ^9 Y# y1 l, D! U* _8
6 N4 y: v; D/ Y0 Y  U% J) T9
9 t% d5 t$ q+ {/ Y) Z10
; o4 s( S6 U& \  L11
12
13
14
5 ^& T$ k( H' n( p( s# l+ p* ?15
16
17
+ Y7 T* |+ C, x1 C18
19
. y$ E/ {8 e- S# J20
7 z; ~. p" }# o' Q( @- A& k, O$ w21
+ N5 t' h/ A' B3 _% }3 d' Q. }三、改进的算法——KMP算法
" Z: o1 q0 V8 x, e& }朴素算法理解简单，但两个串都有依次遍历，时间复杂度为O(n*m)，效率不高。由此有了KMP算法。
8 j2 e& e9 \6 Z! u一般的，在一次匹配中，我们是不知道主串的内容的，而模式串是我们自己定义的。
1 m. R$ [) Z0 F# R( Z9 `1 R朴素算法中，P的第j位失配，默认的把P串后移一位。
! Z. e3 t% `  F# j3 d: G! H但在前一轮的比较中，我们已经知道了P的前(j-1)位与S中间对应的某(j-1)个元素已经匹配成功了。这就意味着，在一轮的尝试匹配中，我们get到了主串的部分内容，我们能否利用这些内容，让P多移几位(我认为这就是KMP算法最根本的东西)，减少遍历的趟数呢？答案是肯定的。再看下面改进后的动图：
9 n( Z1 c0 {- V3 t1 r/ o' ~



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

相比朴素算法：
朴素算法： 每次失配，S串的索引i定位的本次尝试匹配的第一个字符的后一个。P串的索引j定位到1；T(n)=O(n*m)
KMP算法： 每次失配，S串的索引i不动，P串的索引j定位到某个数。T(n)=O(n+m)，时间效率明显提高
$ M2 n/ U; _% v

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

& R. H  I3 h5 c- s# O1 M7 S. u4 y
2 ^2 r$ G& ?4 d, R6 S. R开——始——划——重——点！（图对逻辑关系比较好理解，但i和j的关系对后面求next的算法好理解！）

. A6 E7 l* d+ B0 V8 L
7 T) e* q' G: a+ q. q1 A  u比如，Pj处失配，绿色的是Pj，则我们可以确定P1…Pj-1是与Si…Si+j-2相对应的位置一一相等的

# `' c- `4 N7 u! p  F
- T6 x! }6 R- H2 a& q5 `( z
假设P1…Pj-1中，P1…Pk-1与Pj-k+1…Pj-1是一一相等的，为了下面说的清楚，我们把这种关系叫做“首尾重合”
3 [+ ~3 @6 y  I% _6 s& `) g2 n/ W
- u  O2 i' O3 B- K% C
" B/ c2 w9 B/ B- \1 T  I/ x5 b

那么可以推出，P1…Pk-1与Si…Si+j-2
( v4 h. A, y2 i' e; U6 w+ t
7 m7 c/ Y$ Z" I; p

8 q( i% ?: Q9 F) N
显然，接下来要做的就是把模式串右移了，移到哪里就不用多说了：
$ O2 T: T$ d' ]- P4 r" r7 Q
* r9 q6 S8 g  s  E0 e5 s/ @: v

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


0 k/ u6 m; {4 M* Q( _/ ~8 S3 O' i最后，如果我们知道了一个字符串的next值，那么KMP算法也就很好懂了。相比朴素算法，当发生失配时，i不变，j=next[j]就好啦！接下来就是怎么确定next值了。
/ z' l0 `) Q1 g7 y0 r- B; E6 y0 k+ k" N

四、手动写出一个串的next值
我们规定任何一个串，next[1]=0。(不用next[0]，与串的所有对应)，仍是一张动图搞定问题：

) u/ }6 |, j: e6 }2 W% c5 D' N
这个扫一眼就能依次写出，会了这个方法，应付个期末考试没问题了。


+ j' i1 o9 z* \; ]通过把next值“看”出来，我们再来分析next值，这就很容易得到超级有名的公式了，这个式子对后面的算法理解很重要！所以先要看懂这个式子，如果上面的内容通下来了，这个应该很容易看懂了：
- t) I" `) K& r8 b* W) i


5 @0 }; f, L" u
2 o# |. ^/ j) g' A4 Y; Z+ L五、求next的算法
: h8 }( d+ Z% E" g+ L) k- b2 h% g终于到了最后了~短的串的next值我们可以“看”出来，但长的串就需要借助程序了，具体算法刚接触的时候确实不容易理解，但给我的体验，把上面的内容写完，现在感觉简简单单了…先附上程序再做解释，(终于到了传说中的整整5行代码让我整理了一下午)。


int GetNext(char ch[],int cLen,int next[]){//cLen为串ch的长度
# h/ ~: T9 R" ]/ g1 V    next[1] = 0;
    int i = 1,j = 0;
$ w, `6 p. L* E9 W7 ?0 z! P+ E    while(i<=cLen){
        if(j==0||ch==ch[j]) next[++i] = ++j;
1 F: e. |, q6 B) @9 ]; }# a        else j = next[j];
8 s. c) }1 ]; k# S9 L    }
}
/ g: f8 w6 p1 p# j+ u% u
. x) W, G5 V9 T& f$ q还是先由一般再推优化：
  X; F* c) p, x2 B: s. Y直接求next[j+1]（至于为什么是j+1，是为了和下面的对应）
根据之前的分析，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
…
…
…
else if(P1P2 == Pj-1Pj) => next[j+1]=3
else if(P1 == Pj-1) => next[j+1]=2
5 B5 n" e( d3 \7 t- Telse if(P1 != Pj-1) => next[j+1]=1
每次前去尾1个，后掐头1个，直至得到next[j+1]
- s8 ~$ D  B+ @2 A; R  o# ^

+ Q7 |! H% Z( B1 {再进一步想，next值是一个“工具”，我们单独的求next[j+1]是完全没有意义的，就是说要求next就要把所有j的next求出来。所有一般的，我们都是已知前j个元素的next值，求next[j+1]，以此递推下去，求完整的next数组。
但是，上面的思考过程还是最根本的。所以问题变为两个：知道前j个元素的next的情况下，
. C. A) ~) q* Q6 r1 J+ d* R2 N1 y  l3 f①next[j+1]的可能的最大值是多少（即从哪开始验证）
②某一步验证失败后，需要“前去尾几个，后掐头几个？”（即本次验证失败后，再验证哪个值）
/ X! y( V. u2 L" M+ T3 k6 f! E5 e看一下的分析：
0 ~/ r( t; N1 k8 l- o) A6 B+ q
  E8 m( r$ t$ o; e
' b' E* n: g/ D* g7 e6 W5 y1、next[j+1]的最大值为next[j]+1。
# h8 r7 R* j$ k3 z7 G因为：
假设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
( R3 R9 y' K" c1 t2、如果Pk1≠Pj，那么next[j+1]可能的次大值为next[next[j]]+1，以此类推即可高效求出next[j+1]
这里不好解释，直接看下面的流程分析及图解

; ?) Z9 T- z: R8 `  }. `6 x
开——始——划——重——点！
9 L/ J/ e& `# J4 D$ ?9 m# }$ ^从头走一遍流程
' \3 C1 i( O& L; E, w①求next[j+1]，设值为m
, k- n% y! S& ]②已知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，否则
# D5 x/ @1 f0 K: ~④已知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 即四段重合
4 ~* T- `) ?5 I⑥这时候，再判断如果Pk2=Pj，则P1…Pk2-1P~k2 = Pj-k2+1…Pj-1Pj，则next[j+1]=k2+1；否则再取next[k2]=k3…以此类推
$ I0 e) \- S  l; E+ x4 @
2 `$ |- W4 h: I7 m% M
5 `+ P" ]3 D. \) ?1 G8 \上面几步，耐心看下来，结合那个式子很容易看懂。最后，再加一个图的模拟帮助理解：
1 J& `: h: _: r: \5 I# D. P1、要求next[k+1] 其中k+1=17


  S4 N5 }# h$ E2、已知next[16]=8，则元素有以下关系：
! G2 l; a/ }" Q4 a& F8 i. `

: T! g& d# O6 X) K) d3、如果P8=P16，则明显next[17]=8+1=9
$ @' L. k$ f' m4、如果不相等，又若next[8]=4，则有以下关系

3 o! ^, ~5 C5 Y* s& C, V: `
又加上2的条件知
4 Z& R9 k% c3 B2 f5 v

5 g; R, H* @, K6 O/ k主要是为了证明：
+ f" i2 B/ O* ?

0 Q9 ?8 N! X6 o" ^0 }6 B5、现在在判断，如果P16=P4则next[17]=4+1=5，否则，在继续递推
7 O5 V7 W1 [$ w6、若next[4]=2，则有以下关系
" ^6 y8 K, y. R3 \# H, p. O& V
7 C! w: q  g2 P: e3 n/ g& j: T( ?' ?9 G
7、若P16=P2，则next[17]=2+1=3;否则继续取next[2]=1、next[1]=0；遇到0时还没出结果，则递推结束，此时next[17]=1。最后，再返回看那5行算法，应该很容易明白了！
————————————————
版权声明：本文为CSDN博主「Sirm23333」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_37969433/article/details/82947411


2 z6 `- Y2 o( I' u3 T