数学建模社区-数学中国

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

---

作者: 杨利霞    时间: 2021-8-10 16:12
标题: （算法）通俗易懂的字符串匹配KMP算法及求next值算法
（算法）通俗易懂的字符串匹配KMP算法及求next值算法
/ r5 r8 _5 n, K2 c
大多数据结构课本中，串涉及的内容即串的模式匹配，需要掌握的是朴素算法、KMP算法及next值的求法。在考研备考中，参考严奶奶的教材，我也是在关于求next值的算法中卡了一下午时间，感觉挺有意思的，把一些思考的结果整理出来，与大家一起探讨。


本文的逻辑顺序为
1、最基本的朴素算法
; d8 T. T/ K8 S" P# @/ [2、优化的KMP算法
  }# @# H' N# a) {; U6 I" [3、应算法需要定义的next值
5 u! \3 B% U; q; ~4、手动写出较短串的next值的方法
6 |. f% I  F  H+ S) A: l+ e( a5、最难理解的、足足有5行的代码的求next值的算法
1 F0 ?- C6 C- J% R所有铺垫为了最后的第5点，我觉得以这个逻辑下来，由果索因还是相对好理解的，下面写的很通俗，略显不专业…
( g$ m  P: e2 b; ^9 _4 d
6 ^0 I7 c+ ?8 I! j9 L( [
$ _9 o6 W! I* Q1 G9 G一、问题描述
5 G/ n4 }7 h9 ~# |" m" ^4 q给定一个主串S及一个模式串P，判断模式串是否为主串的子串；若是，返回匹配的第一个元素的位置（序号从1开始），否则返回0；如S=“abcd”，P=“bcd”，则返回2；S=“abcd”，P=“acb”，返回0。

  v$ _: g3 S0 o
二、朴素算法
最简单的方法及一次遍历S与P。以S=“abcabaaaabaaacac”,P="abaabcac"为例，一张动图模拟朴素算法：
% t: P2 L  {  r% f3 Z


9 Y- r0 z5 J, |& n6 r8 d
- x4 ^( g" Y; X$ x8 P这个算法简单，不多说，附上代码

5 R/ d  X' ~1 o4 i9 A$ y, e0 b: U
#include<stdio.h>
int Index_1(char s[],int sLen,char p[],int pLen){//s为主串，sLen为主串元素个数，p为模式串，pLen为模式串的个数
3 ~8 i! n3 P$ D5 D2 z    if(sLen<pLen)return 0;
; A! O+ ]! n# u3 s    int i = 1,j = 1;
; [# ^$ T$ A! ^* n8 z% H( A7 W& \    while(i<=sLen && j<=pLen){
% l3 j+ a; ^- E8 q% D4 R, m        if(s==p[j]){i++;j++;}
        else{
            i = i-j+2;
; V0 K) o2 M, P$ o; p            j = 1;
! e, w) K' R; g% U: ]- }        }
    }
" r" w( R# K& f+ N( Z4 }    if(j>pLen) return i-pLen;
    return 0;
}
void main(){
) G7 B# I$ Q9 I; s) T  @    char s[]={' ','a','b','c','a','b','a','a','a','a','b','a','a','b','c','a','c'};//从序号1开始存
, Q  J" U+ d+ F    char p[]={' ','a','b','a','a','b','c','a','c'};
    int sLen = sizeof(s)/sizeof(char)-1;
    int pLen = sizeof(p)/sizeof(char)-1;
* V2 \, Q8 q9 R( g6 i1 z) T9 x( {    printf("%d",Index_1(s,sLen,p,pLen));
}
+ y( n) [1 B  S3 @2 ^% u1
: A" ]1 }6 `1 z2 q( {) E' w9 `3 i2
( W2 z. j- I, J3
4
5
6
7
8
9
10
11
12
13
14
2 z1 D; q0 d5 ]8 U, F8 H8 g15
: b6 e, m* E# j9 ]7 V8 X* [16
& d% D" K- [+ R" h$ U17
! j3 g" q' N/ v18
+ {- P! e: O' h; Z7 C19
20
4 l5 U5 N9 Q% k, A1 _21
; o* C! x. c0 T% F9 ^3 H三、改进的算法——KMP算法
( P; Y  T$ ?4 V( Q3 h3 b2 [朴素算法理解简单，但两个串都有依次遍历，时间复杂度为O(n*m)，效率不高。由此有了KMP算法。
一般的，在一次匹配中，我们是不知道主串的内容的，而模式串是我们自己定义的。
朴素算法中，P的第j位失配，默认的把P串后移一位。
7 D1 A( @% U1 B8 ^8 f% l1 g( e+ H但在前一轮的比较中，我们已经知道了P的前(j-1)位与S中间对应的某(j-1)个元素已经匹配成功了。这就意味着，在一轮的尝试匹配中，我们get到了主串的部分内容，我们能否利用这些内容，让P多移几位(我认为这就是KMP算法最根本的东西)，减少遍历的趟数呢？答案是肯定的。再看下面改进后的动图：
- Q, I* _6 Y. h4 N

* M1 \) @9 G  y; y. s
$ M+ R4 ^8 e7 m3 W  f
这个模拟过程即KMP算法，若没有看明白，继续往下看相应的解释，理解需要把P多移几位，然后回头再看一遍这个图就很明了了。


0 j7 C0 }  T8 B( J& j. A相比朴素算法：
朴素算法： 每次失配，S串的索引i定位的本次尝试匹配的第一个字符的后一个。P串的索引j定位到1；T(n)=O(n*m)
/ P7 ]; }  Q4 Q. iKMP算法： 每次失配，S串的索引i不动，P串的索引j定位到某个数。T(n)=O(n+m)，时间效率明显提高
- p6 ]3 I  L* z6 ~
5 g6 _3 n+ K$ c
! Z, ?( S) L7 p. z* v而这“定位到某个数”，这个数就是接下来引入的next值。（实际上也就是P往后移多少位，换一种说法罢了：从上图中也可以看出，失配时固定i不变，令S与P[某个数]对齐，实际上是P右移几位的另一种表达，只有为什么这么表达，当然是因为程序好写。）

9 @, y- M8 h" `; U; a8 H
8 b; ~9 [; t, K4 P/ Y8 @; L8 q开——始——划——重——点！（图对逻辑关系比较好理解，但i和j的关系对后面求next的算法好理解！）

, P) ]+ O9 K. T% P) m1 H
比如，Pj处失配，绿色的是Pj，则我们可以确定P1…Pj-1是与Si…Si+j-2相对应的位置一一相等的


/ K. a, q+ s8 D+ Y! H
3 N/ a( \; U8 q  K) \  _$ Q假设P1…Pj-1中，P1…Pk-1与Pj-k+1…Pj-1是一一相等的，为了下面说的清楚，我们把这种关系叫做“首尾重合”
) O) w3 s* H  N3 o& e8 C
! T3 B( E3 Y/ ?8 A; R0 r
1 x/ e  C) A/ `6 ?

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

1 ?" R% f6 T0 g0 p$ E1 K8 F


显然，接下来要做的就是把模式串右移了，移到哪里就不用多说了：

/ O: m: _! ]1 A- U: ^, l


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

, E5 r, N$ O( L# W
最后，如果我们知道了一个字符串的next值，那么KMP算法也就很好懂了。相比朴素算法，当发生失配时，i不变，j=next[j]就好啦！接下来就是怎么确定next值了。
! F& Q, z$ b1 m  q3 N1 k* @8 m

3 U  O6 f6 I! Y( y& O8 w四、手动写出一个串的next值
我们规定任何一个串，next[1]=0。(不用next[0]，与串的所有对应)，仍是一张动图搞定问题：
% C# }+ y8 ]: g9 F
9 Z$ }; W* [, l! o2 b4 w6 j( H
这个扫一眼就能依次写出，会了这个方法，应付个期末考试没问题了。


通过把next值“看”出来，我们再来分析next值，这就很容易得到超级有名的公式了，这个式子对后面的算法理解很重要！所以先要看懂这个式子，如果上面的内容通下来了，这个应该很容易看懂了：
& S9 G5 N1 p8 C8 m; K* n4 o3 ^0 c


6 T3 ?* m# X; M
) |0 }/ e& U4 e4 j5 S% x) y五、求next的算法
终于到了最后了~短的串的next值我们可以“看”出来，但长的串就需要借助程序了，具体算法刚接触的时候确实不容易理解，但给我的体验，把上面的内容写完，现在感觉简简单单了…先附上程序再做解释，(终于到了传说中的整整5行代码让我整理了一下午)。

: k) ]8 c& b& x. z% E) m
int GetNext(char ch[],int cLen,int next[]){//cLen为串ch的长度
7 J) I: y, }7 n( [% E( D    next[1] = 0;
    int i = 1,j = 0;
& I: W+ g: ]; n/ N1 r; V    while(i<=cLen){
, S6 Y* D- X. e  x8 i        if(j==0||ch==ch[j]) next[++i] = ++j;
( ?- l, o' u1 t9 w        else j = next[j];
    }
8 i' K& r4 z0 x; T( p6 b}
4 c; X( d5 x# d$ ^
1 b% w) ^% E& K4 [  V还是先由一般再推优化：
7 B% a5 m5 a  l1 z7 z0 m直接求next[j+1]（至于为什么是j+1，是为了和下面的对应）
- W  D: q6 b% K& l# i0 B根据之前的分析，next[j+1]的值为pj+1的前j个元素的收尾重合的最大个数加一。即需要满足两个条件，把它的值一步步“检验”出来。一是“个数最多”的，因此要从可能的最大值开始验；二是“首尾重合”，因此要一一对应验是否相等。
: a  X" Z8 k8 T9 M1 F9 w不难理解，next[j+1]的最大值为j，所有我们从next[j+1]=j开始“验证”。有以下优先判断顺序：
if(P1…Pj-1 == P2…Pj) => next[j+1]=j
9 O% j2 E& I0 helse if(P1…Pj-2 == P3…Pj) =>next[j+1]=j-1
else if(P1…Pj-3 == P4…Pj) =>next[j+1]=j-2
5 d& ~3 m* v% ~) N0 K( k, B…
  n( L/ U6 \5 q" k8 H…
…
else if(P1P2 == Pj-1Pj) => next[j+1]=3
9 ^$ t% T3 a% @+ [: {- [* \else if(P1 == Pj-1) => next[j+1]=2
else if(P1 != Pj-1) => next[j+1]=1
每次前去尾1个，后掐头1个，直至得到next[j+1]
" l% C9 m4 Q, s" a" V

再进一步想，next值是一个“工具”，我们单独的求next[j+1]是完全没有意义的，就是说要求next就要把所有j的next求出来。所有一般的，我们都是已知前j个元素的next值，求next[j+1]，以此递推下去，求完整的next数组。
' C$ ?0 l3 N/ H2 R1 V但是，上面的思考过程还是最根本的。所以问题变为两个：知道前j个元素的next的情况下，
①next[j+1]的可能的最大值是多少（即从哪开始验证）
②某一步验证失败后，需要“前去尾几个，后掐头几个？”（即本次验证失败后，再验证哪个值）
# D4 f# {4 X# V$ D# |; q0 D看一下的分析：
: }3 i+ J/ A1 X) M, Y- |* T
6 V0 v. k% h& D& T7 \
* y8 _* L1 Y8 b) h5 S5 [2 d+ U1、next[j+1]的最大值为next[j]+1。
7 T" @" L6 l2 s6 b因为：
6 ]* q  K( S& Y' I' S- s假设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 A0 V9 U! t- {% S* f2、如果Pk1≠Pj，那么next[j+1]可能的次大值为next[next[j]]+1，以此类推即可高效求出next[j+1]
这里不好解释，直接看下面的流程分析及图解

0 s( R- w$ c7 _( k1 W) c' ]( r+ k, i. F
9 z1 e2 f$ x  n1 r/ l开——始——划——重——点！
3 p; U/ g) g2 U& M& Y; {从头走一遍流程
3 d1 u5 h( U# ^$ R" O( T5 N①求next[j+1]，设值为m
6 y7 Q7 t" q6 n& J/ ~  l$ e②已知next[j]=k1，则有P1…Pk1-1 = Pj-k1+1…Pj-1
* p- T/ y0 |& a1 \: g% o0 B" U% a③如果Pk1=Pj，则P1…Pk1-1PK = Pj-k1+1…Pj-1Pj，则next[j+1]=k1+1，否则
. h) R- E% W- A, w" g④已知next[k1]=k2，则有P1…Pk2-1 = Pk1-k2+1…Pk1-1
⑤第二第三步联合得到:
* v5 V( j: V  n% w5 ]P1…Pk2-1 = Pk1-k2+1…Pk1-1 = Pj-k1+1…Pk2-k1+j-1 = Pj-k2+1…Pj-1 即四段重合
8 N% N3 V5 v+ j1 _! R⑥这时候，再判断如果Pk2=Pj，则P1…Pk2-1P~k2 = Pj-k2+1…Pj-1Pj，则next[j+1]=k2+1；否则再取next[k2]=k3…以此类推
9 y& K, }8 w; B9 m7 Z

$ j$ U) d% k6 G8 L" Q5 k; Y; r) V  I上面几步，耐心看下来，结合那个式子很容易看懂。最后，再加一个图的模拟帮助理解：
! E  h0 j" v+ V8 @% f# t" C# |' U' N) U1、要求next[k+1] 其中k+1=17

7 g& L+ M6 l4 q  x, G6 C5 S* V
) ]6 O1 b8 R- X2、已知next[16]=8，则元素有以下关系：

% L0 F% P3 b& j8 Z' E
9 |; a! B1 ?5 s+ E3、如果P8=P16，则明显next[17]=8+1=9
4、如果不相等，又若next[8]=4，则有以下关系
5 O! @* Z5 s; G. D( P! s

4 B6 q, q6 i- j+ h7 v又加上2的条件知

" ]$ X! @5 K( [$ U
5 m0 H0 @# P/ n# F2 D主要是为了证明：

' _+ b3 w$ T% W- p, T* }
5、现在在判断，如果P16=P4则next[17]=4+1=5，否则，在继续递推
6、若next[4]=2，则有以下关系

( {+ M! M! m& X4 {
7、若P16=P2，则next[17]=2+1=3;否则继续取next[2]=1、next[1]=0；遇到0时还没出结果，则递推结束，此时next[17]=1。最后，再返回看那5行算法，应该很容易明白了！
————————————————
6 J3 O8 Y8 {% K/ {/ T版权声明：本文为CSDN博主「Sirm23333」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
4 Y+ `) F; ~1 V原文链接：https://blog.csdn.net/qq_37969433/article/details/82947411
( g# V( m% l  L, q) b* u. G

0 U# d% h+ O" D

---

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

Powered by Discuz! X2.5