数学建模社区-数学中国

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

---

作者: 杨利霞    时间: 2021-8-10 16:12
标题: （算法）通俗易懂的字符串匹配KMP算法及求next值算法
（算法）通俗易懂的字符串匹配KMP算法及求next值算法
, f9 N5 w# r9 K" O9 ?/ c2 K
大多数据结构课本中，串涉及的内容即串的模式匹配，需要掌握的是朴素算法、KMP算法及next值的求法。在考研备考中，参考严奶奶的教材，我也是在关于求next值的算法中卡了一下午时间，感觉挺有意思的，把一些思考的结果整理出来，与大家一起探讨。
3 b0 r4 w# b5 `1 w1 h$ m

) Q' f" d9 V* R# k: F2 N本文的逻辑顺序为
1、最基本的朴素算法
4 \  G$ E! ~% C2、优化的KMP算法
2 d" t! m- H3 k* b. \3、应算法需要定义的next值
4、手动写出较短串的next值的方法
* z! @# c4 x- L9 \! y, K- P" |5、最难理解的、足足有5行的代码的求next值的算法
所有铺垫为了最后的第5点，我觉得以这个逻辑下来，由果索因还是相对好理解的，下面写的很通俗，略显不专业…
: L4 H- I/ W$ H; G/ F, ~3 z

+ s, p7 `6 P' x. W! ~3 I一、问题描述
! M# g5 i6 U( i9 J0 u* _给定一个主串S及一个模式串P，判断模式串是否为主串的子串；若是，返回匹配的第一个元素的位置（序号从1开始），否则返回0；如S=“abcd”，P=“bcd”，则返回2；S=“abcd”，P=“acb”，返回0。


# P& t5 N* B7 x二、朴素算法
最简单的方法及一次遍历S与P。以S=“abcabaaaabaaacac”,P="abaabcac"为例，一张动图模拟朴素算法：
" x0 x% _# w+ @+ C- }2 L# V2 S5 n

. H5 a( ?( U1 N2 c1 ^0 D2 ]

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

* h5 F6 Q. k! a4 _. C# S
#include<stdio.h>
+ ^2 y3 y- {/ ^int Index_1(char s[],int sLen,char p[],int pLen){//s为主串，sLen为主串元素个数，p为模式串，pLen为模式串的个数
9 ~- J! d% l3 `5 o; I    if(sLen<pLen)return 0;
    int i = 1,j = 1;
    while(i<=sLen && j<=pLen){
        if(s==p[j]){i++;j++;}
  Q" R0 c1 m6 ?! S' y0 j        else{
* H& I+ B5 r. x+ p            i = i-j+2;
            j = 1;
( ?9 a4 u/ f' a: I  f0 s        }
5 k/ G9 e" W, D1 S& p    }
) d6 u' n3 y& R$ {    if(j>pLen) return i-pLen;
    return 0;
! o+ M1 [# i; B. p( f- P}
4 ?9 \+ t' F% f; Q2 A# Z/ nvoid main(){
& F5 `$ M& u& V7 x0 X& `" j6 Y    char s[]={' ','a','b','c','a','b','a','a','a','a','b','a','a','b','c','a','c'};//从序号1开始存
' X7 o& A/ K: _7 u2 C- m    char p[]={' ','a','b','a','a','b','c','a','c'};
! L2 _  L! k- G* F! U# k# o7 d- a    int sLen = sizeof(s)/sizeof(char)-1;
+ M: w8 G3 o8 w  p* U/ ~    int pLen = sizeof(p)/sizeof(char)-1;
9 d: @5 O  ~( n6 Y) \' e8 T    printf("%d",Index_1(s,sLen,p,pLen));
! C( z$ V6 Q; ]}
6 K- ]" ]) d; @1
9 \$ {* w) M. W; X2
3
4
5
6
* A' j- _5 p3 `3 _) M4 f5 d! @7
8
9
10
& R1 S  y# A+ h  p7 E: ]11
; e& T# h* l1 S5 c  `9 y7 `& G12
* C* `" p+ {* A13
+ w. H: j) S, H" M14
15
16
& A- {/ z& U2 d17
* x2 r. N) R' i% z$ P18
5 L6 {" g; T$ `8 [% @+ _19
20
, ~4 \5 O8 L1 _1 X21
! G, p* X: e8 M, v$ D2 i三、改进的算法——KMP算法
朴素算法理解简单，但两个串都有依次遍历，时间复杂度为O(n*m)，效率不高。由此有了KMP算法。
( d* r, u. u" }' B一般的，在一次匹配中，我们是不知道主串的内容的，而模式串是我们自己定义的。
' S% H* `: t) ?. I朴素算法中，P的第j位失配，默认的把P串后移一位。
但在前一轮的比较中，我们已经知道了P的前(j-1)位与S中间对应的某(j-1)个元素已经匹配成功了。这就意味着，在一轮的尝试匹配中，我们get到了主串的部分内容，我们能否利用这些内容，让P多移几位(我认为这就是KMP算法最根本的东西)，减少遍历的趟数呢？答案是肯定的。再看下面改进后的动图：
& C0 n/ \* D: C
$ r! H4 Q* u, ^  S$ y4 m0 |9 m
' E* p8 R# K2 h1 n/ R4 h
7 Y/ `  I# u5 F/ G% N
这个模拟过程即KMP算法，若没有看明白，继续往下看相应的解释，理解需要把P多移几位，然后回头再看一遍这个图就很明了了。


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

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


开——始——划——重——点！（图对逻辑关系比较好理解，但i和j的关系对后面求next的算法好理解！）
5 T+ P" r- X) A! t- M

0 ^7 j! R+ K- D) j1 Q比如，Pj处失配，绿色的是Pj，则我们可以确定P1…Pj-1是与Si…Si+j-2相对应的位置一一相等的
" D4 p% A; [6 m
& w0 f/ e/ m4 ^& j& L9 \  K( X
7 c4 w* \9 p% Z7 a7 @+ `5 y
假设P1…Pj-1中，P1…Pk-1与Pj-k+1…Pj-1是一一相等的，为了下面说的清楚，我们把这种关系叫做“首尾重合”
% c1 _. H: o' ^2 W6 X8 s5 w1 D6 {+ c+ s
9 M) H* R4 p$ y3 X) u' M


那么可以推出，P1…Pk-1与Si…Si+j-2
! }) {. f# a0 G# D. f
: ~6 }" @3 ]4 O; P4 r
4 A& N+ O5 i3 z; ?; n
* K/ ?" [$ M9 h6 \0 A: b( o6 u
显然，接下来要做的就是把模式串右移了，移到哪里就不用多说了：
8 j0 y. x! W8 s0 D
& V7 r1 S' N: y
$ d% V4 S5 p' q

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


/ `1 y/ E& M2 O, J+ O( n最后，如果我们知道了一个字符串的next值，那么KMP算法也就很好懂了。相比朴素算法，当发生失配时，i不变，j=next[j]就好啦！接下来就是怎么确定next值了。


! \/ H- w: @: J. _9 |2 d四、手动写出一个串的next值
我们规定任何一个串，next[1]=0。(不用next[0]，与串的所有对应)，仍是一张动图搞定问题：
. O' N* W. Y" I9 ?1 l
' u3 M0 ^0 }9 B# c8 p2 z1 w+ ^
/ ^, c* i: D% U/ J2 J+ c这个扫一眼就能依次写出，会了这个方法，应付个期末考试没问题了。

6 \$ e7 q. F% M1 L) w% L" j
通过把next值“看”出来，我们再来分析next值，这就很容易得到超级有名的公式了，这个式子对后面的算法理解很重要！所以先要看懂这个式子，如果上面的内容通下来了，这个应该很容易看懂了：
+ U( Z! z! I, j4 p
8 g  s7 _0 x/ S2 F
) ^$ I  d( P5 p( [$ I2 o. ?+ b3 h

五、求next的算法
终于到了最后了~短的串的next值我们可以“看”出来，但长的串就需要借助程序了，具体算法刚接触的时候确实不容易理解，但给我的体验，把上面的内容写完，现在感觉简简单单了…先附上程序再做解释，(终于到了传说中的整整5行代码让我整理了一下午)。


$ A+ B& M* Q( Y1 \  Mint GetNext(char ch[],int cLen,int next[]){//cLen为串ch的长度
2 k: O5 F( g! \# M2 y    next[1] = 0;
    int i = 1,j = 0;
0 h+ c: J6 L0 M4 O8 Y    while(i<=cLen){
        if(j==0||ch==ch[j]) next[++i] = ++j;
; z0 d  i4 b6 Y        else j = next[j];
    }
}
4 k# K; ]1 Z; M/ d
' H0 Z  H# s$ f% s) A# X! {$ K还是先由一般再推优化：
8 x5 Z9 ^6 R4 m" k+ m+ U直接求next[j+1]（至于为什么是j+1，是为了和下面的对应）
1 m# @! v) a- t  m2 y) }根据之前的分析，next[j+1]的值为pj+1的前j个元素的收尾重合的最大个数加一。即需要满足两个条件，把它的值一步步“检验”出来。一是“个数最多”的，因此要从可能的最大值开始验；二是“首尾重合”，因此要一一对应验是否相等。
不难理解，next[j+1]的最大值为j，所有我们从next[j+1]=j开始“验证”。有以下优先判断顺序：
5 n+ k: i( G+ ^0 [if(P1…Pj-1 == P2…Pj) => next[j+1]=j
8 I3 D7 e5 v, b# j. ?4 Zelse if(P1…Pj-2 == P3…Pj) =>next[j+1]=j-1
$ V% P! R+ D) e7 s! b8 z- felse if(P1…Pj-3 == P4…Pj) =>next[j+1]=j-2
1 M. V5 ^2 S- R2 l$ X…
4 }( I) p1 W6 A" I, _2 Z. R' F; g…
…
! m5 h  X8 ?2 \  x0 h1 i2 T2 nelse 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
每次前去尾1个，后掐头1个，直至得到next[j+1]
  O5 t2 L( E1 A8 h

再进一步想，next值是一个“工具”，我们单独的求next[j+1]是完全没有意义的，就是说要求next就要把所有j的next求出来。所有一般的，我们都是已知前j个元素的next值，求next[j+1]，以此递推下去，求完整的next数组。
  a. ^' K0 f4 ?3 e4 z但是，上面的思考过程还是最根本的。所以问题变为两个：知道前j个元素的next的情况下，
( b) ^. a, S0 T2 P①next[j+1]的可能的最大值是多少（即从哪开始验证）
②某一步验证失败后，需要“前去尾几个，后掐头几个？”（即本次验证失败后，再验证哪个值）
看一下的分析：

- \4 P- {6 x3 l. q! j; H4 u
1、next[j+1]的最大值为next[j]+1。
因为：
假设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
2、如果Pk1≠Pj，那么next[j+1]可能的次大值为next[next[j]]+1，以此类推即可高效求出next[j+1]
这里不好解释，直接看下面的流程分析及图解

: m6 C/ ?! H- ?; O1 r+ j  X) {
" r6 j  o2 q- I5 u开——始——划——重——点！
从头走一遍流程
①求next[j+1]，设值为m
②已知next[j]=k1，则有P1…Pk1-1 = Pj-k1+1…Pj-1
  @) R9 F( v/ Q4 K( j8 |( ^③如果Pk1=Pj，则P1…Pk1-1PK = Pj-k1+1…Pj-1Pj，则next[j+1]=k1+1，否则
+ k5 R0 F$ y; B0 W! E( o- [2 ?④已知next[k1]=k2，则有P1…Pk2-1 = Pk1-k2+1…Pk1-1
⑤第二第三步联合得到:
) I! L- C# g# e6 u: zP1…Pk2-1 = Pk1-k2+1…Pk1-1 = Pj-k1+1…Pk2-k1+j-1 = Pj-k2+1…Pj-1 即四段重合
* ]- ^( N$ d5 k* f* h- \⑥这时候，再判断如果Pk2=Pj，则P1…Pk2-1P~k2 = Pj-k2+1…Pj-1Pj，则next[j+1]=k2+1；否则再取next[k2]=k3…以此类推
+ T& @: H" g' ~, M8 j+ X

3 ?. s; S+ a3 u0 m+ h# A0 P) ?上面几步，耐心看下来，结合那个式子很容易看懂。最后，再加一个图的模拟帮助理解：
1、要求next[k+1] 其中k+1=17


2、已知next[16]=8，则元素有以下关系：


3、如果P8=P16，则明显next[17]=8+1=9
4、如果不相等，又若next[8]=4，则有以下关系


又加上2的条件知
  r5 N4 ?. Y) B) j7 X) U
% V! V1 N- K2 f3 P. |, d4 a6 ]- L2 u
主要是为了证明：

5 u" Y# K! B4 t/ Z) Q* B4 P
! {4 A3 N. q' z# D' T5、现在在判断，如果P16=P4则next[17]=4+1=5，否则，在继续递推
+ m9 T4 _! m$ C( p% J- {$ N# s' d% n6、若next[4]=2，则有以下关系

0 Q  T0 p! g2 j
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版权协议，转载请附上原文出处链接及本声明。
, ]  b4 H7 Q$ F( H, O原文链接：https://blog.csdn.net/qq_37969433/article/details/82947411
* n" w2 I% O; N: ~; u

; Y: }/ Z! J! T/ c/ c

---

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

Powered by Discuz! X2.5