数学建模社区-数学中国

标题: KMP算法—终于全部弄懂了 [打印本页]

---

作者: 杨利霞    时间: 2021-8-10 16:52
标题: KMP算法—终于全部弄懂了
KMP算法—终于全部弄懂了
简介
　　KMP 算法是 D.E.Knuth、J,H,Morris 和 V.R.Pratt 三位神人共同提出的，称之为 Knuth-Morria-Pratt 算法，简称 KMP 算法。该算法相对于 Brute-Force（暴力）算法有比较大的改进，主要是消除了主串指针的回溯，从而使算法效率有了某种程度的提高。


4 B( U) l6 S/ c7 Y: |9 P3 P1 t- d提取加速匹配的信息
7 i6 U# E* T7 \　　上面说道 KMP 算法主要是通过消除主串指针的回溯来提高匹配的效率的，那么，它是则呢样来消除回溯的呢？就是因为它提取并运用了加速匹配的信息！
7 Q$ ^5 s  t3 {& O) h　　这种信息就是对于每模式串 t 的每个元素 t j，都存在一个实数 k ，使得模式串 t 开头的 k 个字符（t 0 t 1…t k-1）依次与 t j 前面的 k（t j-k t j-k+1…t j-1，这里第一个字符 t j-k 最多从 t 1 开始，所以 k < j）个字符相同。如果这样的 k 有多个，则取最大的一个。模式串 t 中每个位置 j 的字符都有这种信息，采用 next 数组表示，即 next[ j ]=MAX{ k }。
9 |* }+ R2 ?$ K% v- ?: j/ q; G　　
; F0 S$ _, q5 f　　加速信息，即数组 next 的提取是整个 KMP 算法中最核心的部分，弄懂了 next 的求解方法，也就弄懂了 KMP 算法的十之七八了，但是不巧的是这部分代码恰恰是最不容易弄懂的……
　　
1 P! c7 H, W9 P4 y+ C7 l3 S先上代码


void Getnext(int next[],String t)
# X% B& }% ?2 q1 X7 w{
   int j=0,k=-1;
/ v3 M- g) X7 @# N3 F& v   next[0]=-1;
5 V3 [$ l0 }! `. f   while(j<t.length-1)
   {
      if(k == -1 || t[j] == t[k])
      {
9 B4 }: V; O; j* U; T         j++;k++;
: R7 O4 y9 N6 J0 h$ D" Y         next[j] = k;
      }
* n1 |$ }- [7 }% g3 X- L      else k = next[k];//此语句是这段代码最反人类的地方，如果你一下子就能看懂，那么请允许我称呼你一声大神！
   }
  U) v; O+ X7 S# W. g. k1 M}
* ?4 Q3 |/ C4 w( K6 P/ Y
ok，下面咱们分三种情况来讲 next 的求解过程
% o1 Z4 D% ?8 e: @2 v

特殊情况
当 j 的值为 0 或 1 的时候，它们的 k 值都为 0，即 next[0] = 0、next[1] =0。但是为了后面 k 值计算的方便，我们将 next[0] 的值设置成 -1。

6 P8 z/ a$ {# l" D
当 t[j] == t[k] 的情况
举个栗子

观察上图可知，当 t[j] == t[k] 时，必然有"t[0]…t[k-1]" == " t[j-k]…t[j-1]"，此时的 k 即是相同子串的长度。因为有"t[0]…t[k-1]" == " t[j-k]…t[j-1]"，且 t[j] == t[k]，则有"t[0]…t[k]" == " t[j-k]…t[j]"，这样也就得出了next[j+1]=k+1。

: L7 H8 E9 p) s. w) m( X
& ?9 }, o1 [2 a: r! g( t( D' E当t[j] != t[k] 的情况
  x4 B, X2 c& h5 \5 y' E3 x关于这种情况，在代码中的描述就是“简单”的一句 k = next[k]；。我当时看了之后，感觉有点蒙，于是就去翻《数据结构教程》。但是这本书里，对于这行代码的解释只有三个字：k 回退…！于是我从“有点蒙”的状态升级到了“很蒙蔽”的状态，我心想，k 回退？我当然知道这是 k 退回，但是它为什么要会退到 next[k] 的位置？为什么不是回退到k-1？？？巴拉巴拉巴拉…此处省略一万字。
: ^0 X( L+ L, }
+ \% L& o& I! x& U0 \
' j4 k/ ^: t+ S$ `+ S9 X我绞尽脑汁，仍是不得其解。于是我就去问度娘…
在我看了众多博客之后，终于有了一种拨云见日的感觉，看下图

　　 由第2中情况可知，当 t[j] == t[k] 时，t[j+1] 的最大子串的长度为 k，即 next[j+1] = k+1。但是此时t[j] != t[k] 了，所以就有 next[j+1] < k，那么求 next[j+1] 就等同于求 t[j] 往前小于 k 个的字符（包括t[j]，看上图蓝色框框）与 t[k] 前面的字符（绿色框框）的最长重合串，即 t[j-k+1] ~ t[j] 与 t[0] ~ t[k-1] 的最长重合串（这里所说“最长重合串”实不严谨，但你知道是符合 k 的子串就行…），那么就相当于求 next[k]（只不过 t[k] 变成了 t[j],但是 next[k] 的值与 t[k] 无关）!!!。所以才有了这句 k = next[k]，如果新的一轮循环（这时 k = next[k] ，j 不变）中 t[j] 依然不等于 t[k] ，则说明倒数第二大 t[0~next[k]-1] 也不行，那么 k 会继续被 next[k] 赋值（这就是所谓的 k 回退…），直到找到符合重合的子串或者 k == -1。
4 @+ a/ \" u3 o6 k8 e) ~# u

至此，算是把求解数组 next 的算法弄清楚了（其实是，终于把 k = next[k] 弄懂了…）

: C9 w6 I* j: `  z6 r: S, D  _) f
; e; c% [- W% ?0 @6 c因为这个算法神奇难解之处就在k=next[k]这一处的理解上，网上解析的非常之多，有的就是例证，举例子按代码走流程，走出结果了，跟肉眼看的一致，就认为解释了为什么k=next[k]；很少有看到解释的非常清楚的，或者有，但我没有仔细和耐心看下去。我一般扫一眼，就大概知道这个解析是否能说的通。仔细想了三天，搞的千转百折，山重水复，一头雾气缭绕的。搞懂以后又觉得确实简单，但是绕人，烧脑。
7 @$ k  M. N/ I- \

9 s+ v* \: B2 O5 i& ?0 M0 P* d再此特别感谢昵称为“sofu6”的博客园主，正是他的博客，让我这愚笨的脑袋瓜开窍了
! r0 d* V# W/ I+ T! P
/ t  h9 C0 q& @% m  b- C1 `
8 ~7 b7 P8 l7 [' }) H. gKMP算法实现
当你求出了 next 数组之后，KMP 算法就很轻易搞定了，下面我用三张图，让你明白 KMP 算法完成匹配的整个过程。
' [0 G- C$ O' j% T. H( E以目标串：s，指针为 i ；模式串：t 指针为 j ; 为例
2 b6 M) X: x2 x- r
上图表示：“si-j ~ si-1” == “t 0 ~ t j-1”，s i != t j（前面都相等，但比较到 t j 时发现不相等了）且next[j] == k。
. {1 W) s( p  Q! g( V2 f' e+ d+ |
根据 next 数组的定义得知 “t k ~ t j-1” == “t 0 ~ t k-1”，所以 “t 0 ~ t k-1” == “si-k ~ si-1”
' T  [9 w9 T0 y
将模式串右移，得到上图，这样就避免了目标穿的指针回溯。
0 l, _2 C$ l: U0 n# v/ x$ X

- A3 ?% i0 \' P  I. k, G# z" ~都明了之后就可以手写 KMP 的代码了

6 F6 B( w- Y. {' J8 x
int KMP(String s,String t)
2 S3 w1 e; p" |6 P7 r{
' t0 h7 F; K+ o9 O1 z0 ^   int next[MaxSize],i=0;j=0;
   Getnext(t,next);
- ]* i$ U$ P2 C' I   while(i<s.length&&j<t.length)
' o- n* i6 @( ]. O/ ~' L% ~   {
: N' `. c  A/ F; B7 z& [      if(j==-1 || s==t[j])
      {
6 W4 R( W9 z) T+ q$ T         i++;
         j++;
% z" Y! ^; J3 w* ]4 n      }
0 V7 x1 S# Z2 V. I      else j=next[j];               //j回退。。。
  D: n, B+ {* E# S! k6 Y: T   }
   if(j>=t.length)
* @! C. b! `/ t1 a' D& U' F       return (i-t.length);         //匹配成功，返回子串的位置
5 [5 k- p( n9 B9 L( u+ n+ P   else
* I  ^/ P) \: V; F8 Z( g      return (-1);                  //没找到
  F/ D. {+ g% y" Q# H4 P}

5 B  v& j2 F" T6 ], M改进后的 next 求解方法
& ^( ]1 b) B. j! E' |" @先来看一下上面算法存在的缺陷：
7 d  }( L1 e  v, R) f" M$ @$ b/ C
显然，当我们上边的算法得到的next数组应该是[ -1，0，0，1 ]

8 Y4 X! Z& ^0 v5 V
所以下一步我们应该是把j移动到第1个元素咯：
  \' C0 Q+ F/ @3 I% [' h+ Q
" @' I4 M1 h, Z不难发现，这一步是完全没有意义的。因为后面的B已经不匹配了，那前面的B也一定是不匹配的，同样的情况其实还发生在第2个元素A上。


显然，发生问题的原因在于t[j] == t[next[j]]。

+ r1 a* Y9 X" \( V8 K# A! u
& F, x7 H% x+ p6 t0 C所以我们需要谈价一个判断：
1 d. y4 @+ ~* Z: ?: T! a6 t' u$ w

void Getnext(int next[],String t)
{
) n" w9 {  B! M) c   int j=0,k=-1;
   next[0]=-1;
   while(j<t.length-1)
   {
      if(k == -1 || t[j] == t[k])
9 x! f& J1 p2 z& M, Q      {
4 M8 Y& P& G5 {1 p2 {- P" S. K6 p$ |: ^         j++;k++;
  R8 q. W, Y  f5 I' b* `% |3 e         if(t[j]==t[k])//当两个字符相同时，就跳过
            next[j] = next[k];
) e8 e, C9 U! l7 o5 ^- I1 O         else
            next[j] = k;
      }
      else k = next[k];
   }
, K6 h* c: i5 A( {4 @  _* r}
: t* F; U% t% G7 t7 M7 `1 j( l2 F————————————————
版权声明：本文为CSDN博主「June·D」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
$ f* S/ a! S& W2 }8 T9 @原文链接：https://blog.csdn.net/dark_cy/article/details/88698736


+ F! ^  {3 q8 z  i, x2 z' N4 q

---

作者: 1051373629    时间: 2021-8-17 17:11
zanzanzanzanzan
3 R- ?4 ]/ H  V; [

---

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

Powered by Discuz! X2.5