数学建模社区-数学中国

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

---

作者: 杨利霞    时间: 2021-8-10 16:12
标题: （算法）通俗易懂的字符串匹配KMP算法及求next值算法
（算法）通俗易懂的字符串匹配KMP算法及求next值算法

; q. s1 T' a3 y% j0 N) t% \( q大多数据结构课本中，串涉及的内容即串的模式匹配，需要掌握的是朴素算法、KMP算法及next值的求法。在考研备考中，参考严奶奶的教材，我也是在关于求next值的算法中卡了一下午时间，感觉挺有意思的，把一些思考的结果整理出来，与大家一起探讨。
% K4 g( I; z0 S( d; X  d( R

! w# f6 U, |- @! `6 X7 V% l本文的逻辑顺序为
* u7 P  C7 L( I1、最基本的朴素算法
9 _& ]/ x" H8 v" K, g9 j2、优化的KMP算法
4 l0 @3 E( C. l0 S+ p  I3、应算法需要定义的next值
( r/ g9 i$ l& O" \4、手动写出较短串的next值的方法
5、最难理解的、足足有5行的代码的求next值的算法
  e% r: K  O# {4 ]! c所有铺垫为了最后的第5点，我觉得以这个逻辑下来，由果索因还是相对好理解的，下面写的很通俗，略显不专业…

8 v' I1 Z! R& b7 y! k
4 s! \( ^; D& e' b一、问题描述
给定一个主串S及一个模式串P，判断模式串是否为主串的子串；若是，返回匹配的第一个元素的位置（序号从1开始），否则返回0；如S=“abcd”，P=“bcd”，则返回2；S=“abcd”，P=“acb”，返回0。

5 N/ B1 h4 q! B/ u+ b8 \
& q8 t7 l! _# ?+ r- U7 B$ j二、朴素算法
最简单的方法及一次遍历S与P。以S=“abcabaaaabaaacac”,P="abaabcac"为例，一张动图模拟朴素算法：
) }) R) U# q1 |1 l  F
) O  Y' B' Y* c5 C* R
5 X) f" Y, j5 J

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

7 p# |3 s! ?6 X" y( A
$ g4 l& |9 k9 l3 ^& ~. Z#include<stdio.h>
! P# Q$ q% U/ z8 k& ?9 W/ \int Index_1(char s[],int sLen,char p[],int pLen){//s为主串，sLen为主串元素个数，p为模式串，pLen为模式串的个数
! z3 N9 F' V4 E) @- z! M6 k! i: h    if(sLen<pLen)return 0;
    int i = 1,j = 1;
    while(i<=sLen && j<=pLen){
& Q% N% v6 U1 Y1 _% [5 X8 F        if(s==p[j]){i++;j++;}
        else{
            i = i-j+2;
: B' N3 J" s9 Q3 ^/ ^$ ~            j = 1;
# J0 c6 l& n" @0 P: X        }
    }
    if(j>pLen) return i-pLen;
    return 0;
$ `& p6 u' `+ E}
; M5 A0 _& N& |void main(){
- S5 u9 r! J$ I    char s[]={' ','a','b','c','a','b','a','a','a','a','b','a','a','b','c','a','c'};//从序号1开始存
0 ?) b& o) w$ _4 H, W5 g+ e0 D, L9 [    char p[]={' ','a','b','a','a','b','c','a','c'};
    int sLen = sizeof(s)/sizeof(char)-1;
4 l$ Y' R5 a" K" Z    int pLen = sizeof(p)/sizeof(char)-1;
    printf("%d",Index_1(s,sLen,p,pLen));
3 ?/ g3 z# y( b) X* T# ~}
6 _+ z/ T3 t) b6 G& \1
" a; A; r/ P9 D; J2
3
' C$ q) e6 ]6 z2 ?* @/ v3 G% `4
5
$ t9 N% D/ [( w& Z, _8 @0 X: H. A6
7
8
/ L' Z3 k7 l, E5 \3 b! d9
10
11
+ b; ]  b$ D) N# S9 |& T" E# y12
13
1 `( [" k7 v8 `: z; V14
/ L' P4 s9 q9 b15
. N; Y. [/ i. v5 U% g: h16
* F0 X! h8 b& B3 U  o+ Z4 a17
18
& q2 Z$ o2 V: J) h3 J+ u19
+ y$ C$ u1 Z$ l) m# ^5 \( g+ m20
4 m- p/ x  t+ \7 ?21
三、改进的算法——KMP算法
朴素算法理解简单，但两个串都有依次遍历，时间复杂度为O(n*m)，效率不高。由此有了KMP算法。
一般的，在一次匹配中，我们是不知道主串的内容的，而模式串是我们自己定义的。
$ h4 p. P# R7 u, B# d朴素算法中，P的第j位失配，默认的把P串后移一位。
! ^8 r0 S4 N1 g- u但在前一轮的比较中，我们已经知道了P的前(j-1)位与S中间对应的某(j-1)个元素已经匹配成功了。这就意味着，在一轮的尝试匹配中，我们get到了主串的部分内容，我们能否利用这些内容，让P多移几位(我认为这就是KMP算法最根本的东西)，减少遍历的趟数呢？答案是肯定的。再看下面改进后的动图：


/ z2 i/ i7 l9 ^' n. l

这个模拟过程即KMP算法，若没有看明白，继续往下看相应的解释，理解需要把P多移几位，然后回头再看一遍这个图就很明了了。
' a" s! T* T0 |: ~
" g, V. V- K: e: \# k! {4 A
& S4 q4 X* N* z% @7 }相比朴素算法：
朴素算法： 每次失配，S串的索引i定位的本次尝试匹配的第一个字符的后一个。P串的索引j定位到1；T(n)=O(n*m)
KMP算法： 每次失配，S串的索引i不动，P串的索引j定位到某个数。T(n)=O(n+m)，时间效率明显提高
8 Z. p8 ]" K+ C3 N
" ?; h4 _" _+ q3 V0 @
而这“定位到某个数”，这个数就是接下来引入的next值。（实际上也就是P往后移多少位，换一种说法罢了：从上图中也可以看出，失配时固定i不变，令S与P[某个数]对齐，实际上是P右移几位的另一种表达，只有为什么这么表达，当然是因为程序好写。）
$ ~; Z* J- q: I% P1 Y7 [: H) N' V

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

: p' u) K/ i: v' I
9 U7 p. h" W) O1 }比如，Pj处失配，绿色的是Pj，则我们可以确定P1…Pj-1是与Si…Si+j-2相对应的位置一一相等的


# K  G* b( k/ z# t- a; D3 o6 L
假设P1…Pj-1中，P1…Pk-1与Pj-k+1…Pj-1是一一相等的，为了下面说的清楚，我们把这种关系叫做“首尾重合”
/ `. I  H9 @- O  C+ y+ V



那么可以推出，P1…Pk-1与Si…Si+j-2



! }% N* J9 l' v& s' H6 [
显然，接下来要做的就是把模式串右移了，移到哪里就不用多说了：


: F- Y5 X& ]" ?( I2 ?
' l8 P3 H$ k' m6 O# R# g
# M+ I8 W7 d/ b% o4 j* h5 m: k0 E为了表示下一轮比较j定位的地方，我们将其定义为next[j]，next[j]就是第j个元素前j-1个元素首尾重合部分个数加一，当然，为了能遍历完整，首尾重合部分的元素个数应取到最多，即next[j]应取尽量大的值，原因挺好理解的，可以想个例子模拟一下，会完美跳过正确结果。在上图中就是绿色元素的next值为蓝色元素的序号。也即，对于字符串P，next[8]=4。如此，再看一下上面的动图是不是清楚了不少。
* z1 Z/ B& [1 N7 b" s, ^' X

最后，如果我们知道了一个字符串的next值，那么KMP算法也就很好懂了。相比朴素算法，当发生失配时，i不变，j=next[j]就好啦！接下来就是怎么确定next值了。
6 [+ ?" W6 K7 h( Q4 C
: b* A" d" Q; M, r; s/ e! k
四、手动写出一个串的next值
' ^3 G$ A! t9 Z我们规定任何一个串，next[1]=0。(不用next[0]，与串的所有对应)，仍是一张动图搞定问题：

( z! O- b9 N) X8 s
这个扫一眼就能依次写出，会了这个方法，应付个期末考试没问题了。
% D8 Y5 j/ \7 e. G
' n6 B+ Z4 s7 n/ W- l; Z
2 ~! Y) j. ?8 c/ M4 \5 B* J! O通过把next值“看”出来，我们再来分析next值，这就很容易得到超级有名的公式了，这个式子对后面的算法理解很重要！所以先要看懂这个式子，如果上面的内容通下来了，这个应该很容易看懂了：


( y8 L" P5 x2 D7 e- w
- E1 m; k* P6 E/ z- y
五、求next的算法
- g+ j, S' X  v3 x9 P4 h9 o终于到了最后了~短的串的next值我们可以“看”出来，但长的串就需要借助程序了，具体算法刚接触的时候确实不容易理解，但给我的体验，把上面的内容写完，现在感觉简简单单了…先附上程序再做解释，(终于到了传说中的整整5行代码让我整理了一下午)。
2 {" A$ t8 {( w

3 C% h: [9 P8 y. c% c  Xint GetNext(char ch[],int cLen,int next[]){//cLen为串ch的长度
3 q( R9 }8 e7 U( G& P: ]    next[1] = 0;
( L* j7 E1 H* f8 t  }    int i = 1,j = 0;
    while(i<=cLen){
; P( r" w/ `1 R( i        if(j==0||ch==ch[j]) next[++i] = ++j;
. Y1 b7 e. q0 K# s        else j = next[j];
    }
: e9 a+ t; S/ }2 h. @}
: F/ [* O1 {$ z
. O* C% {8 V; Q% N  J  S5 Y1 w还是先由一般再推优化：
直接求next[j+1]（至于为什么是j+1，是为了和下面的对应）
$ x5 X) ~1 |: O( h6 k根据之前的分析，next[j+1]的值为pj+1的前j个元素的收尾重合的最大个数加一。即需要满足两个条件，把它的值一步步“检验”出来。一是“个数最多”的，因此要从可能的最大值开始验；二是“首尾重合”，因此要一一对应验是否相等。
$ l( x% e) B! n& @  N不难理解，next[j+1]的最大值为j，所有我们从next[j+1]=j开始“验证”。有以下优先判断顺序：
if(P1…Pj-1 == P2…Pj) => next[j+1]=j
6 a% \& T6 I( q  Selse if(P1…Pj-2 == P3…Pj) =>next[j+1]=j-1
else if(P1…Pj-3 == P4…Pj) =>next[j+1]=j-2
…
  X% C, _  `3 R" o…
) l- J0 O) J: A+ _9 x# z! L) l8 w…
: f* @0 e. F, p' l/ L4 telse if(P1P2 == Pj-1Pj) => next[j+1]=3
% ]0 d' W5 `; U' ]else if(P1 == Pj-1) => next[j+1]=2
else if(P1 != Pj-1) => next[j+1]=1
. i8 M$ n4 d: _6 D  r每次前去尾1个，后掐头1个，直至得到next[j+1]


$ c: s2 Y5 N$ r再进一步想，next值是一个“工具”，我们单独的求next[j+1]是完全没有意义的，就是说要求next就要把所有j的next求出来。所有一般的，我们都是已知前j个元素的next值，求next[j+1]，以此递推下去，求完整的next数组。
但是，上面的思考过程还是最根本的。所以问题变为两个：知道前j个元素的next的情况下，
- u- a& v/ `' ~0 c' l) T7 ^, @3 g7 K①next[j+1]的可能的最大值是多少（即从哪开始验证）
$ x' H, n9 ^0 ~* p②某一步验证失败后，需要“前去尾几个，后掐头几个？”（即本次验证失败后，再验证哪个值）
看一下的分析：
$ m% @4 q4 ?: Z" P) _2 Z! J0 Q: b5 l

1、next[j+1]的最大值为next[j]+1。
: T" {& |9 j1 e: a& r! C因为：
假设next[j]=k1，则可以说明P1…Pk1-1=Pj-k1+1…Pj-1，且这是前j个元素最大的首尾重合序列。
' L0 G) \! w# _5 l2 D' ^5 d6 y3 r如果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]
这里不好解释，直接看下面的流程分析及图解
% g8 J9 K1 g5 x1 D

- _- i6 M. f2 j开——始——划——重——点！
6 h* ]9 o6 J  a) T% K4 F# _/ x从头走一遍流程
, O; j, B2 P. u①求next[j+1]，设值为m
! Q$ S" @9 m) Z$ n. X* A1 s②已知next[j]=k1，则有P1…Pk1-1 = Pj-k1+1…Pj-1
) i0 Y/ f4 i; i/ [: s③如果Pk1=Pj，则P1…Pk1-1PK = Pj-k1+1…Pj-1Pj，则next[j+1]=k1+1，否则
5 x8 [+ s8 K# q5 t- z! @' j④已知next[k1]=k2，则有P1…Pk2-1 = Pk1-k2+1…Pk1-1
, u7 V2 L( \& O: I' ^6 |⑤第二第三步联合得到:
P1…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…以此类推

2 R& M: @" z  _& c% K  K5 {5 O
0 a# L& T) m* i; _& N) @7 F( j2 k上面几步，耐心看下来，结合那个式子很容易看懂。最后，再加一个图的模拟帮助理解：
1、要求next[k+1] 其中k+1=17
/ T$ ]$ w6 J* W/ w& T+ w
  ?. b7 y; L5 k- n
4 @( V  B1 ^* |3 M# }, J2、已知next[16]=8，则元素有以下关系：


3、如果P8=P16，则明显next[17]=8+1=9
# m, f* l. \6 I; g0 M2 m4 Q- w4、如果不相等，又若next[8]=4，则有以下关系
* v1 e6 @- P+ H! Y1 u

又加上2的条件知
; e+ I6 ?- ~* r' B, S7 c! {

: ^) }6 c# [" p" x; W3 F) ^主要是为了证明：


5 C" ^$ w' X& ?- S) w& O( H% f5、现在在判断，如果P16=P4则next[17]=4+1=5，否则，在继续递推
0 G$ _' @; _) H8 V6、若next[4]=2，则有以下关系
1 U' u$ y  Y( M! a& Y5 Y- T- q2 A

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版权协议，转载请附上原文出处链接及本声明。
9 }! b0 w% p  r  S原文链接：https://blog.csdn.net/qq_37969433/article/details/82947411

$ V* Y' M' M. R
1 ~% }' W) y$ o9 D! ~) H4 m
: G1 a$ u1 q! S4 N" M

---

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

Powered by Discuz! X2.5