KMP算法—终于全部弄懂了

杨利霞

KMP算法—终于全部弄懂了
3 w7 D* i0 L1 y5 w3 g% @% [% z简介
  X- Q! E; {% j( R) t1 N: j　　KMP 算法是 D.E.Knuth、J,H,Morris 和 V.R.Pratt 三位神人共同提出的，称之为 Knuth-Morria-Pratt 算法，简称 KMP 算法。该算法相对于 Brute-Force（暴力）算法有比较大的改进，主要是消除了主串指针的回溯，从而使算法效率有了某种程度的提高。
( l& M$ a- x- b; O7 Q* D
4 G# K6 P: G  x. v6 K1 I3 k* }
提取加速匹配的信息
3 F' J5 R! ]* M6 @$ i7 b% U* `　　上面说道 KMP 算法主要是通过消除主串指针的回溯来提高匹配的效率的，那么，它是则呢样来消除回溯的呢？就是因为它提取并运用了加速匹配的信息！
　　这种信息就是对于每模式串 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 }。
; @& U' n$ @! p' |/ F" j. ]. L　　
) J7 g) F" X1 ~9 r# T# n　　加速信息，即数组 next 的提取是整个 KMP 算法中最核心的部分，弄懂了 next 的求解方法，也就弄懂了 KMP 算法的十之七八了，但是不巧的是这部分代码恰恰是最不容易弄懂的……
　　
; u- o6 r, t' T先上代码


void Getnext(int next[],String t)
! z$ g+ r* E6 w7 g/ h1 v{
   int j=0,k=-1;
   next[0]=-1;
   while(j<t.length-1)
   {
' w/ x; X; j. ~+ g, y* l' ~* l      if(k == -1 || t[j] == t[k])
  M* k) d0 D+ Q0 B3 l      {
" t3 i4 _: n; _' C! Z. I& Z         j++;k++;
- P8 r: E* M; D5 _1 n2 ]9 ~1 `. X& J         next[j] = k;
      }
: k2 J0 R0 P1 U! X& l7 ^# u      else k = next[k];//此语句是这段代码最反人类的地方，如果你一下子就能看懂，那么请允许我称呼你一声大神！
5 ~! z$ e1 l: m: O' }   }
) R+ \" ~4 b  o8 y) q, _}

; J: R" H1 S# }/ nok，下面咱们分三种情况来讲 next 的求解过程
. u5 S* J/ t9 [$ F3 C

特殊情况
当 j 的值为 0 或 1 的时候，它们的 k 值都为 0，即 next[0] = 0、next[1] =0。但是为了后面 k 值计算的方便，我们将 next[0] 的值设置成 -1。
* \8 T7 x1 W& y+ s, Q
5 y* |9 m& d: h! v
- z9 L* S; h) [3 I3 g当 t[j] == t[k] 的情况
举个栗子
) G$ @; G7 e' N1 D- f
观察上图可知，当 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。
5 G9 t$ b- L  R8 Z  A: r
. }- F4 [0 p/ F. L" U3 E
( D4 @% W! \3 V  S当t[j] != t[k] 的情况
% E# i; ^) z7 S8 }; X关于这种情况，在代码中的描述就是“简单”的一句 k = next[k]；。我当时看了之后，感觉有点蒙，于是就去翻《数据结构教程》。但是这本书里，对于这行代码的解释只有三个字：k 回退…！于是我从“有点蒙”的状态升级到了“很蒙蔽”的状态，我心想，k 回退？我当然知道这是 k 退回，但是它为什么要会退到 next[k] 的位置？为什么不是回退到k-1？？？巴拉巴拉巴拉…此处省略一万字。

+ K& |, ^, r$ G- V3 v
+ _7 N  U/ e1 I+ w4 @我绞尽脑汁，仍是不得其解。于是我就去问度娘…
  }8 w; M* {6 h' f" h3 i: n2 `在我看了众多博客之后，终于有了一种拨云见日的感觉，看下图
" o0 M. S* S- [+ K( V: H/ I+ C
　　 由第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。
& {& q( r. T4 {) R6 [; H/ H
: x' l, p" T0 X/ t2 \
5 e1 ~& Z- }9 J! w  r至此，算是把求解数组 next 的算法弄清楚了（其实是，终于把 k = next[k] 弄懂了…）

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

8 s0 ^' v! m  b$ T( @7 d
再此特别感谢昵称为“sofu6”的博客园主，正是他的博客，让我这愚笨的脑袋瓜开窍了
) x, `/ ^2 S0 N9 Y

KMP算法实现
当你求出了 next 数组之后，KMP 算法就很轻易搞定了，下面我用三张图，让你明白 KMP 算法完成匹配的整个过程。
' d# U: z& v3 F2 T( v( I以目标串：s，指针为 i ；模式串：t 指针为 j ; 为例

) U# o2 w/ t% y- ]上图表示：“si-j ~ si-1” == “t 0 ~ t j-1”，s i != t j（前面都相等，但比较到 t j 时发现不相等了）且next[j] == k。

根据 next 数组的定义得知 “t k ~ t j-1” == “t 0 ~ t k-1”，所以 “t 0 ~ t k-1” == “si-k ~ si-1”
& Q% Y0 y0 c8 |, n  k) k
3 W4 o3 ^" ^8 Q# m, b将模式串右移，得到上图，这样就避免了目标穿的指针回溯。


6 Y$ `: u0 g, B! I! B' n都明了之后就可以手写 KMP 的代码了

# I! H. s5 l; c. h" @
3 u0 e+ N- l" X2 Q- ]int KMP(String s,String t)
: g9 I) @. o, D{
   int next[MaxSize],i=0;j=0;
5 u4 d1 A, n  z+ ?8 y/ T" `$ k" }' h   Getnext(t,next);
   while(i<s.length&&j<t.length)
   {
      if(j==-1 || s==t[j])
" v+ W+ z' V1 J7 N      {
8 ]; ~; L3 K; J, ^! }# E3 i         i++;
         j++;
      }
( h' y' X( ?; ]      else j=next[j];               //j回退。。。
   }
   if(j>=t.length)
8 C) d% a8 F& p) n9 [       return (i-t.length);         //匹配成功，返回子串的位置
) G' d3 e, h1 W$ `4 c& g   else
" C$ C6 w* k, F/ z      return (-1);                  //没找到
}
- b1 F# v& _+ I7 D  S. r8 `" ]! e
改进后的 next 求解方法
/ O4 B& ^& I. Y4 Q' ?: `! x+ z7 P先来看一下上面算法存在的缺陷：
0 T$ t7 u# X4 C+ m. ]: E
: K# O1 ]5 z5 K5 v显然，当我们上边的算法得到的next数组应该是[ -1，0，0，1 ]

9 c0 H# G* X$ p& C
& }$ |9 J, i" D, W9 a7 z所以下一步我们应该是把j移动到第1个元素咯：

/ g. N: x9 K) _- B) s. J5 \+ S不难发现，这一步是完全没有意义的。因为后面的B已经不匹配了，那前面的B也一定是不匹配的，同样的情况其实还发生在第2个元素A上。
; w0 J( A4 T% ]( Q* D
- Y- F' c8 m3 `! z# {! J+ g( Q$ M" Z- S7 k
显然，发生问题的原因在于t[j] == t[next[j]]。
7 D1 y% ^' M+ N+ p
) ?1 u8 a+ k, h5 [$ x& \
( I4 @. E; F- K1 p3 X所以我们需要谈价一个判断：


/ D8 J7 I/ U# X, a( E, X( t+ avoid Getnext(int next[],String t)
  y$ R  H8 c7 D3 D{
4 u6 `0 w) ]+ L. W   int j=0,k=-1;
   next[0]=-1;
   while(j<t.length-1)
   {
      if(k == -1 || t[j] == t[k])
      {
7 h4 ]" H, @3 F/ d         j++;k++;
0 W1 z" c3 c( V& Q" M9 v         if(t[j]==t[k])//当两个字符相同时，就跳过
            next[j] = next[k];
) [- S5 ~* @" K# l0 g: r         else
            next[j] = k;
      }
# s" U; I) f$ ]. s+ P9 Y      else k = next[k];
6 K+ i0 M- D% Y3 d' `0 @$ z   }
}
————————————————
+ A8 j; h7 `9 L# y+ n, ~# X版权声明：本文为CSDN博主「June·D」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/dark_cy/article/details/88698736

4 r4 O  a) O' j
! r0 z( {/ S' e/ h  @  @2 p

1051373629

zanzanzanzanzan
. [! |, O4 Q* b' S* d