KMP算法—终于全部弄懂了

杨利霞

KMP算法—终于全部弄懂了
简介
$ z) U, _- u$ E7 h$ k7 j$ J　　KMP 算法是 D.E.Knuth、J,H,Morris 和 V.R.Pratt 三位神人共同提出的，称之为 Knuth-Morria-Pratt 算法，简称 KMP 算法。该算法相对于 Brute-Force（暴力）算法有比较大的改进，主要是消除了主串指针的回溯，从而使算法效率有了某种程度的提高。
& V# ?) M7 f3 i9 F2 H& N

提取加速匹配的信息
　　上面说道 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 }。
  Q5 k& z* S1 Z+ c* I　　
　　加速信息，即数组 next 的提取是整个 KMP 算法中最核心的部分，弄懂了 next 的求解方法，也就弄懂了 KMP 算法的十之七八了，但是不巧的是这部分代码恰恰是最不容易弄懂的……
　　
先上代码
( H8 o& G% i. ]$ f& Q. x& ^) S
! c' T' h- U, T% g
void Getnext(int next[],String t)
" d6 e% u9 x6 W" t$ ?) P{
; |6 i  }  A9 Z' G+ l9 T   int j=0,k=-1;
# ?* m# n3 q. f2 ~& q) G+ v   next[0]=-1;
   while(j<t.length-1)
' {* l0 f1 ~; {' a   {
      if(k == -1 || t[j] == t[k])
1 s6 u! K! V9 h& N      {
         j++;k++;
( y7 }: ]2 F4 x6 r0 s         next[j] = k;
      }
      else k = next[k];//此语句是这段代码最反人类的地方，如果你一下子就能看懂，那么请允许我称呼你一声大神！
0 w- }/ V- D3 `: ~/ K   }
/ S. @0 y7 G% {: X$ I3 f}

ok，下面咱们分三种情况来讲 next 的求解过程

9 C3 ]2 @  O; [& g* z
* o( F' T. n' a0 p5 M( }特殊情况
当 j 的值为 0 或 1 的时候，它们的 k 值都为 0，即 next[0] = 0、next[1] =0。但是为了后面 k 值计算的方便，我们将 next[0] 的值设置成 -1。

  d- G, J  P6 e' d& _
当 t[j] == t[k] 的情况
7 T% e. p# ?% [; f& K* q举个栗子
6 R3 R" C+ l/ B% D6 F4 r
6 \, m( d  J& v% 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。

. e* k; p- o/ d, S
6 K6 P3 j- R5 b# E( q) k- s& V当t[j] != t[k] 的情况
关于这种情况，在代码中的描述就是“简单”的一句 k = next[k]；。我当时看了之后，感觉有点蒙，于是就去翻《数据结构教程》。但是这本书里，对于这行代码的解释只有三个字：k 回退…！于是我从“有点蒙”的状态升级到了“很蒙蔽”的状态，我心想，k 回退？我当然知道这是 k 退回，但是它为什么要会退到 next[k] 的位置？为什么不是回退到k-1？？？巴拉巴拉巴拉…此处省略一万字。
! h% ~$ `: P+ k2 f
  j* e4 D- L& a
我绞尽脑汁，仍是不得其解。于是我就去问度娘…
5 W- b4 f+ e' D: a7 B% k在我看了众多博客之后，终于有了一种拨云见日的感觉，看下图

' H& L5 S( \! d5 T8 O& Q7 V　　 由第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。

2 l5 g$ J/ K9 a2 a, H
4 Q/ c7 ]& h, x7 m至此，算是把求解数组 next 的算法弄清楚了（其实是，终于把 k = next[k] 弄懂了…）

$ b0 o  X" i. f9 W- E3 u) P
8 V3 s0 v& A; t' ~因为这个算法神奇难解之处就在k=next[k]这一处的理解上，网上解析的非常之多，有的就是例证，举例子按代码走流程，走出结果了，跟肉眼看的一致，就认为解释了为什么k=next[k]；很少有看到解释的非常清楚的，或者有，但我没有仔细和耐心看下去。我一般扫一眼，就大概知道这个解析是否能说的通。仔细想了三天，搞的千转百折，山重水复，一头雾气缭绕的。搞懂以后又觉得确实简单，但是绕人，烧脑。
* E! ~5 |- C% k% l3 s

; w0 H3 l; G. Q# f再此特别感谢昵称为“sofu6”的博客园主，正是他的博客，让我这愚笨的脑袋瓜开窍了
, O9 j- a$ I1 Z( K5 _) s
  h/ `0 P4 T4 n7 b3 d% t* U. |: t5 p
3 W1 q8 o- f! Y) u. jKMP算法实现
+ F8 f$ B7 o) A- \& N, e当你求出了 next 数组之后，KMP 算法就很轻易搞定了，下面我用三张图，让你明白 KMP 算法完成匹配的整个过程。
( r* P; h  N  f" ^+ f5 W* |以目标串：s，指针为 i ；模式串：t 指针为 j ; 为例
% V& u" Z, v8 V' _1 U8 r- L
上图表示：“si-j ~ si-1” == “t 0 ~ t j-1”，s i != t j（前面都相等，但比较到 t j 时发现不相等了）且next[j] == k。
; i' x/ P2 v2 _* [
& r  {" V0 P& l+ l7 h, v" r' Y  k根据 next 数组的定义得知 “t k ~ t j-1” == “t 0 ~ t k-1”，所以 “t 0 ~ t k-1” == “si-k ~ si-1”
6 ]8 B8 w1 p" A0 G4 F: k
将模式串右移，得到上图，这样就避免了目标穿的指针回溯。
  J# ]% ^% h( l/ Q3 Z- K

' N9 ~' W1 t( J. Z  O  B, {7 x都明了之后就可以手写 KMP 的代码了


9 H/ b+ g8 A& A0 F/ P2 M7 Dint KMP(String s,String t)
{
   int next[MaxSize],i=0;j=0;
0 b4 o! }. M; L! b; Y; ~% X   Getnext(t,next);
8 T  m$ |% M, n# E, W2 T" c$ @   while(i<s.length&&j<t.length)
   {
      if(j==-1 || s==t[j])
      {
         i++;
7 l  D$ S" ^7 ^8 ^! f         j++;
  N4 H+ `* u; h: M' ]- x! ^      }
& ]! h' o* L. g3 f/ v7 ]' `      else j=next[j];               //j回退。。。
: D# o$ K5 ?% w* B2 T) A+ Z6 a   }
$ \9 a6 p; p4 s5 g) T- o( Q% S+ E; q* ^   if(j>=t.length)
. C) ?, j7 v3 G( Y       return (i-t.length);         //匹配成功，返回子串的位置
   else
      return (-1);                  //没找到
}
+ s+ `) m1 I" p  {
& G9 P# a$ y% c, R改进后的 next 求解方法
先来看一下上面算法存在的缺陷：
  @$ r9 c& P% i: ]! ~8 y- ]1 ^8 a
显然，当我们上边的算法得到的next数组应该是[ -1，0，0，1 ]
, L: L8 C- |, [, Q

所以下一步我们应该是把j移动到第1个元素咯：
3 Z: g. m6 d; B; I5 M$ U4 y! _
不难发现，这一步是完全没有意义的。因为后面的B已经不匹配了，那前面的B也一定是不匹配的，同样的情况其实还发生在第2个元素A上。
) L0 K+ p( b6 z5 Y9 V) Y7 u

显然，发生问题的原因在于t[j] == t[next[j]]。
0 v, [8 `) U. g( s

所以我们需要谈价一个判断：
" S" x7 k7 m! O5 M6 A

1 j8 V$ Q# v# [( c4 Nvoid Getnext(int next[],String t)
{
   int j=0,k=-1;
5 k; V& Z. A' @9 i( b   next[0]=-1;
: ~$ g" k  _. w9 Q3 h* ~5 ~/ @* a   while(j<t.length-1)
3 s7 w5 A( e7 G: Z0 @  h   {
" K3 B% P# i2 v( S- X" g      if(k == -1 || t[j] == t[k])
6 @0 T/ A# C2 h1 n* Q) \      {
         j++;k++;
8 X+ {: M3 ]* w0 V/ d7 V/ q         if(t[j]==t[k])//当两个字符相同时，就跳过
            next[j] = next[k];
, _9 ~' H. `0 ~  l! T1 X6 ~1 z- q         else
            next[j] = k;
' ^( ?/ f1 U$ i/ _      }
! V- u% L  H* e4 k: a      else k = next[k];
* U9 X8 Q' B, h' Z: p) e   }
. y8 R2 d3 p+ v" j* c}
————————————————
版权声明：本文为CSDN博主「June·D」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/dark_cy/article/details/88698736
3 ?5 G0 X, F. [, ^7 D% w1 S: ~; Y

0 w& p' I5 }6 x2 q' e3 y

1051373629

zanzanzanzanzan
6 K; ]. Q; G5 A0 T1 t