KMP算法—终于全部弄懂了

杨利霞

KMP算法—终于全部弄懂了
简介
　　KMP 算法是 D.E.Knuth、J,H,Morris 和 V.R.Pratt 三位神人共同提出的，称之为 Knuth-Morria-Pratt 算法，简称 KMP 算法。该算法相对于 Brute-Force（暴力）算法有比较大的改进，主要是消除了主串指针的回溯，从而使算法效率有了某种程度的提高。
3 }# S9 h: b* Z! h+ R& ]
3 j# x$ ~$ ?8 `; ^6 b/ d8 ]
2 G. {, w6 D- L/ o提取加速匹配的信息
　　上面说道 KMP 算法主要是通过消除主串指针的回溯来提高匹配的效率的，那么，它是则呢样来消除回溯的呢？就是因为它提取并运用了加速匹配的信息！
2 K0 X6 ]$ A$ _　　这种信息就是对于每模式串 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 }。
　　
　　加速信息，即数组 next 的提取是整个 KMP 算法中最核心的部分，弄懂了 next 的求解方法，也就弄懂了 KMP 算法的十之七八了，但是不巧的是这部分代码恰恰是最不容易弄懂的……
　　
) O" X8 T3 v1 ~! g! x" |% [先上代码

3 f8 a- E6 d9 Y% L+ w, q
void Getnext(int next[],String t)
$ e! Z2 ?8 _8 j) k: w. r{
   int j=0,k=-1;
( o1 A- [0 z3 m$ U& ^0 T6 E   next[0]=-1;
   while(j<t.length-1)
   {
      if(k == -1 || t[j] == t[k])
      {
$ Z4 g% K' J( T' ~# G) c8 J) ?+ o         j++;k++;
% k3 M0 ?  @$ [, j1 m2 d         next[j] = k;
      }
* m5 ]& _) s: N& X+ Q. \' ]      else k = next[k];//此语句是这段代码最反人类的地方，如果你一下子就能看懂，那么请允许我称呼你一声大神！
   }
- Q: `5 w5 A: x# L4 H9 q* Q" I}
4 _' u: |* E0 d- U: `3 \
5 p0 a7 g2 D# j; B  Xok，下面咱们分三种情况来讲 next 的求解过程
+ E- |4 e( T$ q! |
# C% O2 Z% u# A2 }7 Z4 n
特殊情况
当 j 的值为 0 或 1 的时候，它们的 k 值都为 0，即 next[0] = 0、next[1] =0。但是为了后面 k 值计算的方便，我们将 next[0] 的值设置成 -1。
# q6 z4 J  \2 `) S4 a% R8 V

当 t[j] == t[k] 的情况
举个栗子

% b: ?- ^8 s* i- _观察上图可知，当 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。


) ?- T( Q: r& ]5 L当t[j] != t[k] 的情况
关于这种情况，在代码中的描述就是“简单”的一句 k = next[k]；。我当时看了之后，感觉有点蒙，于是就去翻《数据结构教程》。但是这本书里，对于这行代码的解释只有三个字：k 回退…！于是我从“有点蒙”的状态升级到了“很蒙蔽”的状态，我心想，k 回退？我当然知道这是 k 退回，但是它为什么要会退到 next[k] 的位置？为什么不是回退到k-1？？？巴拉巴拉巴拉…此处省略一万字。
7 e4 u0 ~! ~: z& P% j

我绞尽脑汁，仍是不得其解。于是我就去问度娘…
7 F6 v( P/ ~3 F在我看了众多博客之后，终于有了一种拨云见日的感觉，看下图

　　 由第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。
9 E* ]- J' p0 n# o

7 p) R/ e7 s6 k& h& U* K5 p至此，算是把求解数组 next 的算法弄清楚了（其实是，终于把 k = next[k] 弄懂了…）

1 B9 j- o  o! s# p( D* G0 @0 I0 N
因为这个算法神奇难解之处就在k=next[k]这一处的理解上，网上解析的非常之多，有的就是例证，举例子按代码走流程，走出结果了，跟肉眼看的一致，就认为解释了为什么k=next[k]；很少有看到解释的非常清楚的，或者有，但我没有仔细和耐心看下去。我一般扫一眼，就大概知道这个解析是否能说的通。仔细想了三天，搞的千转百折，山重水复，一头雾气缭绕的。搞懂以后又觉得确实简单，但是绕人，烧脑。
# n% ~1 }' E9 G; E( ^# _$ [

再此特别感谢昵称为“sofu6”的博客园主，正是他的博客，让我这愚笨的脑袋瓜开窍了

; ~5 X' Y. J9 Q( e
7 z2 h( ?$ @  pKMP算法实现
当你求出了 next 数组之后，KMP 算法就很轻易搞定了，下面我用三张图，让你明白 KMP 算法完成匹配的整个过程。
+ _( j. \7 K; p以目标串：s，指针为 i ；模式串：t 指针为 j ; 为例
! n1 c8 D) R/ d  Q  b" Z
上图表示：“si-j ~ si-1” == “t 0 ~ t j-1”，s i != t j（前面都相等，但比较到 t j 时发现不相等了）且next[j] == k。
! k1 U8 W7 y, V6 e; g5 l$ t" f+ c% W
根据 next 数组的定义得知 “t k ~ t j-1” == “t 0 ~ t k-1”，所以 “t 0 ~ t k-1” == “si-k ~ si-1”
  x) u! I) R6 Z/ H  `% R
  E' y& p6 Y3 @, D将模式串右移，得到上图，这样就避免了目标穿的指针回溯。
7 u" N# i; U8 c& p, Z  c
" f5 L# x2 D% b4 `4 l  v5 [
都明了之后就可以手写 KMP 的代码了


) X, w2 \# F7 Eint KMP(String s,String t)
9 E8 s8 T  a( `1 }{
$ C2 t* [( U9 D3 F% [9 D; B   int next[MaxSize],i=0;j=0;
" u" Z. V9 x8 _) }3 @  C- n   Getnext(t,next);
8 K" n% F3 |7 J8 p( ~   while(i<s.length&&j<t.length)
$ Q1 @; g/ ^* M   {
      if(j==-1 || s==t[j])
      {
         i++;
         j++;
      }
      else j=next[j];               //j回退。。。
; e; K# I5 n- K0 S% i8 v$ V   }
4 G( O6 K7 v1 ~8 a2 ?0 j: v2 j; }   if(j>=t.length)
1 v1 P& S* j1 {, s: @# G       return (i-t.length);         //匹配成功，返回子串的位置
7 e7 {) l& x  M3 M" R0 M, }/ m5 h   else
, z8 X: E# h1 u& y/ Y      return (-1);                  //没找到
}

0 c5 ]' r! l8 }9 ?6 f- A改进后的 next 求解方法
先来看一下上面算法存在的缺陷：

显然，当我们上边的算法得到的next数组应该是[ -1，0，0，1 ]
" N9 n: x# O& E- Z& i

+ F: P9 @, K* W$ a+ z所以下一步我们应该是把j移动到第1个元素咯：

) ^, l0 r+ n8 M8 ^不难发现，这一步是完全没有意义的。因为后面的B已经不匹配了，那前面的B也一定是不匹配的，同样的情况其实还发生在第2个元素A上。


7 D; u2 b: `0 p显然，发生问题的原因在于t[j] == t[next[j]]。
4 j$ @" ~3 ^7 H7 P9 `

所以我们需要谈价一个判断：
, n9 P9 ^/ Y; x; c3 d7 |  h

) K" P* e. I+ T" ^2 ^  r' svoid Getnext(int next[],String t)
{
' O! Z9 m; ^" R# T! ^6 r! d9 Y, p   int j=0,k=-1;
   next[0]=-1;
   while(j<t.length-1)
, i) s+ A6 ]* ?   {
      if(k == -1 || t[j] == t[k])
      {
4 B3 x( \% v0 v$ s1 x% v         j++;k++;
$ F1 _0 V4 n0 v9 N5 P         if(t[j]==t[k])//当两个字符相同时，就跳过
; L# X8 H0 Q$ I$ C, s; e, A. G1 O* j            next[j] = next[k];
# o0 `4 D# X) x, z         else
$ x- t' R5 z# n$ i1 f% k            next[j] = k;
      }
      else k = next[k];
   }
! O$ C' [7 \; g3 c, M0 v}
. F" J$ U4 e9 e————————————————
- |# m5 {- d$ }$ Q版权声明：本文为CSDN博主「June·D」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
$ o" q! e  a+ W4 O原文链接：https://blog.csdn.net/dark_cy/article/details/88698736
2 n9 U. e+ |) Y! ?; G

1051373629

zanzanzanzanzan
9 g, H, o- F! i& o8 x) U: `) e0 p