数学建模社区-数学中国

标题: （算法）通俗易懂的字符串匹配KMP算法及求next值算法 [打印本页]

---

作者: 杨利霞    时间: 2021-8-10 16:12
标题: （算法）通俗易懂的字符串匹配KMP算法及求next值算法
（算法）通俗易懂的字符串匹配KMP算法及求next值算法
+ I' Q7 y- N- o* ?  Y! k
% H0 ?- W8 d- F$ U. s' _大多数据结构课本中，串涉及的内容即串的模式匹配，需要掌握的是朴素算法、KMP算法及next值的求法。在考研备考中，参考严奶奶的教材，我也是在关于求next值的算法中卡了一下午时间，感觉挺有意思的，把一些思考的结果整理出来，与大家一起探讨。


7 g' e# f* ^$ o2 I2 `本文的逻辑顺序为
1、最基本的朴素算法
& Y1 |/ M' r1 n5 u2、优化的KMP算法
3、应算法需要定义的next值
4、手动写出较短串的next值的方法
$ P7 }% C& y" ]% V5、最难理解的、足足有5行的代码的求next值的算法
所有铺垫为了最后的第5点，我觉得以这个逻辑下来，由果索因还是相对好理解的，下面写的很通俗，略显不专业…

/ ~2 N7 s3 N7 ^) \
一、问题描述
+ A7 _* j* A, c% P6 M给定一个主串S及一个模式串P，判断模式串是否为主串的子串；若是，返回匹配的第一个元素的位置（序号从1开始），否则返回0；如S=“abcd”，P=“bcd”，则返回2；S=“abcd”，P=“acb”，返回0。
9 G6 M" [) N* U2 p

二、朴素算法
最简单的方法及一次遍历S与P。以S=“abcabaaaabaaacac”,P="abaabcac"为例，一张动图模拟朴素算法：


/ @, f7 I' J2 q5 H' _. U
7 e/ ?" W- d  ]0 i5 E" L: `& H3 [, Z
这个算法简单，不多说，附上代码
( H* F: H; }9 Z1 O

! ]: m8 Y% |# v. o# G#include<stdio.h>
int Index_1(char s[],int sLen,char p[],int pLen){//s为主串，sLen为主串元素个数，p为模式串，pLen为模式串的个数
    if(sLen<pLen)return 0;
$ a+ H) ?' H% [6 Z5 E    int i = 1,j = 1;
    while(i<=sLen && j<=pLen){
4 }. r' N: J0 O7 \- _1 k6 _1 K        if(s==p[j]){i++;j++;}
        else{
% W8 {4 s3 D7 F/ Y            i = i-j+2;
            j = 1;
        }
0 m6 D0 Y$ V$ w2 F* S4 v) {/ w4 ?    }
1 T6 g3 p. _( ]! Q" k    if(j>pLen) return i-pLen;
    return 0;
. h9 p" x5 k  _) R3 q4 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'};
9 q2 E3 U  q5 A0 X3 D    int sLen = sizeof(s)/sizeof(char)-1;
    int pLen = sizeof(p)/sizeof(char)-1;
    printf("%d",Index_1(s,sLen,p,pLen));
}
1
2
3
9 |5 P! b: B2 f7 ?2 M4
5
6
7
8
9
10
# J3 w: K! ~& z$ m7 A0 W, I- [5 B4 L) H11
12
4 r1 ?/ L, L5 \, D+ U13
14
15
( ?/ I4 t, B% r5 g' s) L7 W16
17
18
19
0 t, R5 ~0 G& W5 l: F20
21
三、改进的算法——KMP算法
5 v2 u. p6 E+ L: l- E朴素算法理解简单，但两个串都有依次遍历，时间复杂度为O(n*m)，效率不高。由此有了KMP算法。
一般的，在一次匹配中，我们是不知道主串的内容的，而模式串是我们自己定义的。
朴素算法中，P的第j位失配，默认的把P串后移一位。
  X6 t4 n0 g) a* d$ [9 d但在前一轮的比较中，我们已经知道了P的前(j-1)位与S中间对应的某(j-1)个元素已经匹配成功了。这就意味着，在一轮的尝试匹配中，我们get到了主串的部分内容，我们能否利用这些内容，让P多移几位(我认为这就是KMP算法最根本的东西)，减少遍历的趟数呢？答案是肯定的。再看下面改进后的动图：


) s/ {% M; ^+ }8 J& R

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

( P9 r# a: [0 k+ ]  z+ F0 q
相比朴素算法：
朴素算法： 每次失配，S串的索引i定位的本次尝试匹配的第一个字符的后一个。P串的索引j定位到1；T(n)=O(n*m)
" V/ ?# n0 B- I9 h  lKMP算法： 每次失配，S串的索引i不动，P串的索引j定位到某个数。T(n)=O(n+m)，时间效率明显提高


5 g# T/ i1 f2 }, F, i( [而这“定位到某个数”，这个数就是接下来引入的next值。（实际上也就是P往后移多少位，换一种说法罢了：从上图中也可以看出，失配时固定i不变，令S与P[某个数]对齐，实际上是P右移几位的另一种表达，只有为什么这么表达，当然是因为程序好写。）
, Q! k6 M  B; K
9 ]/ ^2 w2 C+ n$ F7 s; }
8 d6 p. |( T. w1 A0 n开——始——划——重——点！（图对逻辑关系比较好理解，但i和j的关系对后面求next的算法好理解！）
" Z5 x- e5 D9 [( \7 m; ^
7 g9 k/ {* s0 f5 n8 ^3 z
比如，Pj处失配，绿色的是Pj，则我们可以确定P1…Pj-1是与Si…Si+j-2相对应的位置一一相等的
* B' A& B& R- `; L! y" f7 Q9 K3 K
( h: d7 b7 `' u2 `
& h  u, {# t8 t- v% Y+ ^: m
7 Y2 W2 C! J1 |/ }$ U& K6 Y; ~& |0 T假设P1…Pj-1中，P1…Pk-1与Pj-k+1…Pj-1是一一相等的，为了下面说的清楚，我们把这种关系叫做“首尾重合”



* `% u% v8 T# A8 F& z
# M$ c1 I5 ]  B2 ]9 n那么可以推出，P1…Pk-1与Si…Si+j-2

: ]2 ]( M- A1 B* k7 l# m9 j


) i5 ]/ Q- |9 A/ |1 f8 _8 ?9 m显然，接下来要做的就是把模式串右移了，移到哪里就不用多说了：

' U. f4 I9 k: u2 Z
5 ], R: g' K8 K  ]

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


2 R1 Q) C+ v7 t* j最后，如果我们知道了一个字符串的next值，那么KMP算法也就很好懂了。相比朴素算法，当发生失配时，i不变，j=next[j]就好啦！接下来就是怎么确定next值了。

2 t3 Y% Q; h: D
四、手动写出一个串的next值
! I0 V4 a' r! G5 H- L, i+ n我们规定任何一个串，next[1]=0。(不用next[0]，与串的所有对应)，仍是一张动图搞定问题：
% A* x. \; r, D
. p% d' o* R* q# j9 X- J) q
这个扫一眼就能依次写出，会了这个方法，应付个期末考试没问题了。

5 o0 p9 ?8 l/ Z  e4 U
通过把next值“看”出来，我们再来分析next值，这就很容易得到超级有名的公式了，这个式子对后面的算法理解很重要！所以先要看懂这个式子，如果上面的内容通下来了，这个应该很容易看懂了：
: i, p: S& @6 N1 ~# v
& f7 V* z( F: b* b
0 |  h5 B9 v9 ]. Q
/ S  R* z* n* i8 d0 w
五、求next的算法
5 h0 u* `# A1 S终于到了最后了~短的串的next值我们可以“看”出来，但长的串就需要借助程序了，具体算法刚接触的时候确实不容易理解，但给我的体验，把上面的内容写完，现在感觉简简单单了…先附上程序再做解释，(终于到了传说中的整整5行代码让我整理了一下午)。
8 D0 [0 L6 C* t3 ]) h/ W! ~. `

int GetNext(char ch[],int cLen,int next[]){//cLen为串ch的长度
    next[1] = 0;
. B) c3 c3 |+ r0 X3 ^0 o    int i = 1,j = 0;
7 J( A9 q6 f! x  B  j    while(i<=cLen){
        if(j==0||ch==ch[j]) next[++i] = ++j;
; o9 h1 ?% W7 d! @$ P% X1 L8 r: {        else j = next[j];
    }
}

8 Q6 H3 ?% V5 C还是先由一般再推优化：
2 q  l4 r2 h) P, e2 M1 ~, U' ^. h2 I  Q直接求next[j+1]（至于为什么是j+1，是为了和下面的对应）
根据之前的分析，next[j+1]的值为pj+1的前j个元素的收尾重合的最大个数加一。即需要满足两个条件，把它的值一步步“检验”出来。一是“个数最多”的，因此要从可能的最大值开始验；二是“首尾重合”，因此要一一对应验是否相等。
不难理解，next[j+1]的最大值为j，所有我们从next[j+1]=j开始“验证”。有以下优先判断顺序：
) T; p7 ?3 W: K8 J6 I* A, x; Z" P/ Bif(P1…Pj-1 == P2…Pj) => next[j+1]=j
+ z/ r% Q. X8 c% @# L1 H  Aelse if(P1…Pj-2 == P3…Pj) =>next[j+1]=j-1
% D) S( X0 n. A# d4 Kelse if(P1…Pj-3 == P4…Pj) =>next[j+1]=j-2
0 C2 u" C, m! C( R9 d& l…
2 k5 f+ [9 ^1 }3 W: S1 f…
' ~; {* [3 S" Q0 N; J, {…
" a* p# j4 K2 C6 |: |; [else if(P1P2 == Pj-1Pj) => next[j+1]=3
else if(P1 == Pj-1) => next[j+1]=2
else if(P1 != Pj-1) => next[j+1]=1
* _" ]6 o# N% B# W5 V% e3 b' Q每次前去尾1个，后掐头1个，直至得到next[j+1]
2 z6 [! W% W! m- F8 H) b% P$ X

再进一步想，next值是一个“工具”，我们单独的求next[j+1]是完全没有意义的，就是说要求next就要把所有j的next求出来。所有一般的，我们都是已知前j个元素的next值，求next[j+1]，以此递推下去，求完整的next数组。
' D2 n8 s7 S6 }% Z但是，上面的思考过程还是最根本的。所以问题变为两个：知道前j个元素的next的情况下，
①next[j+1]的可能的最大值是多少（即从哪开始验证）
6 ]( w4 s- K3 H9 {②某一步验证失败后，需要“前去尾几个，后掐头几个？”（即本次验证失败后，再验证哪个值）
4 G( f) U& X% k看一下的分析：

4 n+ D& _2 J$ G5 N7 \4 i0 n
. g2 W8 a6 L+ _) D5 L# |1、next[j+1]的最大值为next[j]+1。
0 C+ _+ @3 g, A' I$ e因为：
假设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
# }5 L: r* l; Y) K& V/ ~: Y2、如果Pk1≠Pj，那么next[j+1]可能的次大值为next[next[j]]+1，以此类推即可高效求出next[j+1]
这里不好解释，直接看下面的流程分析及图解
3 v/ {% y% k7 J5 K! z# P' B

. t; f# }( e: w' C- W7 S开——始——划——重——点！
4 W+ Y; l' D. {( V( A从头走一遍流程
; }9 C3 M, `5 V- F①求next[j+1]，设值为m
②已知next[j]=k1，则有P1…Pk1-1 = Pj-k1+1…Pj-1
- }$ ~' ?/ C/ k% [5 A- P, T③如果Pk1=Pj，则P1…Pk1-1PK = Pj-k1+1…Pj-1Pj，则next[j+1]=k1+1，否则
4 ]7 K+ ~* _! j6 l, t: g④已知next[k1]=k2，则有P1…Pk2-1 = Pk1-k2+1…Pk1-1
  j( z, V7 j/ k- W⑤第二第三步联合得到:
! d0 e2 ?+ ^. m% AP1…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…以此类推


0 |+ @# I# h. H上面几步，耐心看下来，结合那个式子很容易看懂。最后，再加一个图的模拟帮助理解：
# u4 Y0 X8 `& z6 I, Y3 I1、要求next[k+1] 其中k+1=17
$ ?  J" l& w3 v# Z! o3 W( ]/ w

) a$ q9 e" z& C  w2、已知next[16]=8，则元素有以下关系：
( }, o+ a: {9 j- H8 m% \
# [8 r( V$ j* G0 g4 v9 X
3 Z: K9 }. H" `" D# W3、如果P8=P16，则明显next[17]=8+1=9
9 M# E  R# H$ ]7 @. E+ f6 a+ O4、如果不相等，又若next[8]=4，则有以下关系
1 {- f5 y6 g3 {4 G

/ v9 P( ^8 \( q# ]; e又加上2的条件知
; b( P) \1 m( Q, |" ~

3 G8 m- e" V5 M4 p: x主要是为了证明：
) `  o7 u& }9 p  p9 K

; b, A! g' V& i* x3 A5、现在在判断，如果P16=P4则next[17]=4+1=5，否则，在继续递推
6、若next[4]=2，则有以下关系


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


: q9 i6 Z4 ^# v/ C

---

欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)

Powered by Discuz! X2.5