KMP算法—终于全部弄懂了

杨利霞

KMP算法—终于全部弄懂了
简介
　　KMP 算法是 D.E.Knuth、J,H,Morris 和 V.R.Pratt 三位神人共同提出的，称之为 Knuth-Morria-Pratt 算法，简称 KMP 算法。该算法相对于 Brute-Force（暴力）算法有比较大的改进，主要是消除了主串指针的回溯，从而使算法效率有了某种程度的提高。
. P: u8 X- s' o, _9 N

提取加速匹配的信息
　　上面说道 KMP 算法主要是通过消除主串指针的回溯来提高匹配的效率的，那么，它是则呢样来消除回溯的呢？就是因为它提取并运用了加速匹配的信息！
1 E2 L5 c* N& E  L　　这种信息就是对于每模式串 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 }。
6 d/ F2 A4 y1 d9 B& }　　
　　加速信息，即数组 next 的提取是整个 KMP 算法中最核心的部分，弄懂了 next 的求解方法，也就弄懂了 KMP 算法的十之七八了，但是不巧的是这部分代码恰恰是最不容易弄懂的……
+ g9 w* n! x$ G/ f9 q　　
先上代码


: m8 G* O4 o2 ?2 \void Getnext(int next[],String t)
# O. u. e  F" k$ I5 V/ K2 l0 c{
+ k7 {6 O2 L5 L( G+ O- y   int j=0,k=-1;
% A' y7 z! A. n1 k   next[0]=-1;
+ M" `7 T3 e  E; W8 w+ ]; c  K; }   while(j<t.length-1)
; j6 g0 l9 G$ |5 w   {
5 G2 |3 A, [' ^4 L3 n1 R      if(k == -1 || t[j] == t[k])
9 J+ b  w5 H  y7 W9 w, W6 z% x4 ^      {
- J0 Q1 K5 d6 P2 g3 |- O         j++;k++;
5 S$ n) i6 U8 `- c         next[j] = k;
7 x" b4 D. P' B  j" e8 S2 V+ h      }
- }4 n  x9 _" l3 i' M- H      else k = next[k];//此语句是这段代码最反人类的地方，如果你一下子就能看懂，那么请允许我称呼你一声大神！
   }
0 D# j7 z! r( \}
5 f3 P& @0 d$ B) Z5 |  I
# ], C  T- B1 `$ n# sok，下面咱们分三种情况来讲 next 的求解过程
% s7 ~/ K1 K5 ]& T4 k$ j0 {0 g2 O

+ @7 C0 m0 |' Q" s3 k; h3 S! b1 X特殊情况
当 j 的值为 0 或 1 的时候，它们的 k 值都为 0，即 next[0] = 0、next[1] =0。但是为了后面 k 值计算的方便，我们将 next[0] 的值设置成 -1。
  a9 {) ]+ ^# l2 I7 ^; d& Q& d
/ L! J+ p, O; }0 a
$ H$ l6 q1 R( j1 B5 ~6 e3 O当 t[j] == t[k] 的情况
, ]" w6 {: _1 i$ |举个栗子

) S" |& b9 N% \0 ]% }3 W# R观察上图可知，当 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。

, Y/ I0 W% ~4 M1 z4 T8 L
/ `& }' w6 `2 D; S; X. o: }当t[j] != t[k] 的情况
关于这种情况，在代码中的描述就是“简单”的一句 k = next[k]；。我当时看了之后，感觉有点蒙，于是就去翻《数据结构教程》。但是这本书里，对于这行代码的解释只有三个字：k 回退…！于是我从“有点蒙”的状态升级到了“很蒙蔽”的状态，我心想，k 回退？我当然知道这是 k 退回，但是它为什么要会退到 next[k] 的位置？为什么不是回退到k-1？？？巴拉巴拉巴拉…此处省略一万字。
  h+ V0 n0 O, L  R9 [
8 X0 _! ~" J  H3 H; ^. M
% T  S0 \+ W: o5 w6 Q- U% M我绞尽脑汁，仍是不得其解。于是我就去问度娘…
在我看了众多博客之后，终于有了一种拨云见日的感觉，看下图

　　 由第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。


+ w5 K  N3 {. Q+ E" ]" M! g4 Z/ l至此，算是把求解数组 next 的算法弄清楚了（其实是，终于把 k = next[k] 弄懂了…）
9 m, P: }3 H. Q. u( h" \9 r# m; p

0 \/ s0 d) b9 K* z/ O  l8 A' J因为这个算法神奇难解之处就在k=next[k]这一处的理解上，网上解析的非常之多，有的就是例证，举例子按代码走流程，走出结果了，跟肉眼看的一致，就认为解释了为什么k=next[k]；很少有看到解释的非常清楚的，或者有，但我没有仔细和耐心看下去。我一般扫一眼，就大概知道这个解析是否能说的通。仔细想了三天，搞的千转百折，山重水复，一头雾气缭绕的。搞懂以后又觉得确实简单，但是绕人，烧脑。


再此特别感谢昵称为“sofu6”的博客园主，正是他的博客，让我这愚笨的脑袋瓜开窍了
& U3 W2 ~" h* u  r; C6 G
& g& |( C: x, g8 W
# q6 ^. d/ r6 {5 J4 cKMP算法实现
当你求出了 next 数组之后，KMP 算法就很轻易搞定了，下面我用三张图，让你明白 KMP 算法完成匹配的整个过程。
以目标串：s，指针为 i ；模式串：t 指针为 j ; 为例
2 e+ O( y+ I, a! Q5 n& W4 R0 }5 {8 b
! Y* d5 x" v2 u上图表示：“si-j ~ si-1” == “t 0 ~ t j-1”，s i != t j（前面都相等，但比较到 t j 时发现不相等了）且next[j] == k。
7 W( a3 ?" l* W
7 C% {  Y8 ]7 W* A: W  B根据 next 数组的定义得知 “t k ~ t j-1” == “t 0 ~ t k-1”，所以 “t 0 ~ t k-1” == “si-k ~ si-1”
0 J' ?+ o& t% @+ |1 ?% q
将模式串右移，得到上图，这样就避免了目标穿的指针回溯。

3 g) b$ K! E, W7 o% [
8 |3 K/ s$ s, R都明了之后就可以手写 KMP 的代码了
# o! S) S6 F) B5 ?# ]9 B
) {: H) C, m6 j2 u5 S7 Q" C1 f
int KMP(String s,String t)
/ D9 Z4 k2 |0 k0 T{
   int next[MaxSize],i=0;j=0;
  C. I2 h  Q' n- b  `1 K   Getnext(t,next);
   while(i<s.length&&j<t.length)
   {
      if(j==-1 || s==t[j])
/ r3 M* t% B' G5 i9 O/ Z; |      {
) H( I5 l# y! ]) Z         i++;
3 s! F- e: v: k' L  C8 O         j++;
* m+ X" _9 I+ {; d      }
      else j=next[j];               //j回退。。。
   }
   if(j>=t.length)
       return (i-t.length);         //匹配成功，返回子串的位置
   else
/ Z) q' f3 i+ i1 W      return (-1);                  //没找到
6 o' a3 M5 R! }}

+ m) ^% T( _* K  _6 R# H9 S改进后的 next 求解方法
先来看一下上面算法存在的缺陷：

显然，当我们上边的算法得到的next数组应该是[ -1，0，0，1 ]
# V3 r" e( L% z% z; c2 ?: A
' \) d$ d5 K- ?; w
- y) r0 p# Y8 N- \  n" {5 c所以下一步我们应该是把j移动到第1个元素咯：
  C& r5 C% n( N6 b# B
不难发现，这一步是完全没有意义的。因为后面的B已经不匹配了，那前面的B也一定是不匹配的，同样的情况其实还发生在第2个元素A上。

2 M- E, H8 G- J0 V4 g3 ^/ X
显然，发生问题的原因在于t[j] == t[next[j]]。

. \1 `% e& N  y3 w  R( A, v# ?0 ?
0 j7 U" H3 F7 [: a所以我们需要谈价一个判断：

' o8 F- Z: C0 U; a9 _+ V/ ^: q
+ g$ r" g% X  T$ Cvoid Getnext(int next[],String t)
{
   int j=0,k=-1;
   next[0]=-1;
3 U* v* ]5 v- G3 g& ]. z   while(j<t.length-1)
   {
) \6 M0 B6 w# r% f9 u4 F6 J      if(k == -1 || t[j] == t[k])
      {
$ w- U1 \3 z9 E' c         j++;k++;
6 Z! ?# D8 H/ i* c/ Y5 `2 F$ s4 c         if(t[j]==t[k])//当两个字符相同时，就跳过
$ D. t6 I1 r4 w1 \            next[j] = next[k];
         else
            next[j] = k;
      }
      else k = next[k];
   }
}
4 ?, n9 m9 }! v, N————————————————
版权声明：本文为CSDN博主「June·D」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
# p# h0 \5 D5 E8 n) w4 O原文链接：https://blog.csdn.net/dark_cy/article/details/88698736
! c( _7 C3 {. n& C6 Q7 x5 g* |
+ s+ `4 E; G# V6 \$ B3 B6 T
& u0 d4 \4 {2 [8 j2 @6 v

1051373629

zanzanzanzanzan