KMP算法—终于全部弄懂了

杨利霞

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

1 \% g2 h" N0 I6 N! F
  e! c7 ?9 x% [! g" R提取加速匹配的信息
' c8 T) J: `1 {# t　　上面说道 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 }。
: G/ z- K3 B/ q  k5 H7 }: `- e　　
) ^9 j4 j' T) h6 s* j! ]　　加速信息，即数组 next 的提取是整个 KMP 算法中最核心的部分，弄懂了 next 的求解方法，也就弄懂了 KMP 算法的十之七八了，但是不巧的是这部分代码恰恰是最不容易弄懂的……
　　
先上代码

# s3 ^0 f; f7 I
+ ]% s) B- m; s5 L8 k- o7 B1 tvoid Getnext(int next[],String t)
: Z: x* x, N+ o8 ~) K- b  q: l{
. \  e1 F+ s( M' k. M' l; b   int j=0,k=-1;
   next[0]=-1;
, Q  {, P1 k5 [/ S   while(j<t.length-1)
7 j- |3 M/ u/ l$ d; g* v# r   {
      if(k == -1 || t[j] == t[k])
. w/ o/ e$ [1 l7 K# I      {
6 r& j0 u! U1 d7 F  g! M' I: M         j++;k++;
         next[j] = k;
3 E# M- T: _, x( s# \- f. V0 X2 O$ P1 ~      }
) E- \+ p( s5 ~# i9 m+ ^4 R      else k = next[k];//此语句是这段代码最反人类的地方，如果你一下子就能看懂，那么请允许我称呼你一声大神！
/ x' p4 A; `0 }3 R+ i5 V, X   }
: Q& Y/ e) [1 Y}

ok，下面咱们分三种情况来讲 next 的求解过程
( y* ^" ?; N' N  r+ u5 @! H: R9 U

" r$ n2 g3 X" A% J1 p' U特殊情况
% _8 X, M& a) G5 O3 o1 f7 K当 j 的值为 0 或 1 的时候，它们的 k 值都为 0，即 next[0] = 0、next[1] =0。但是为了后面 k 值计算的方便，我们将 next[0] 的值设置成 -1。
4 ~& X4 n  x, m& T- m1 H7 A+ e
/ e" }% L0 i- V2 J9 b( L
. l2 x7 ~2 s( ]2 N. m当 t[j] == t[k] 的情况
% ?9 b) }, B- {  n. f8 r举个栗子
4 t9 ~5 v2 s4 s) Z, c# }! Z7 `
观察上图可知，当 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) C+ Y: m. n
4 d) c, q8 i* z$ C' O8 U: {
/ Y, |9 e3 Y+ E% z; b当t[j] != t[k] 的情况
关于这种情况，在代码中的描述就是“简单”的一句 k = next[k]；。我当时看了之后，感觉有点蒙，于是就去翻《数据结构教程》。但是这本书里，对于这行代码的解释只有三个字：k 回退…！于是我从“有点蒙”的状态升级到了“很蒙蔽”的状态，我心想，k 回退？我当然知道这是 k 退回，但是它为什么要会退到 next[k] 的位置？为什么不是回退到k-1？？？巴拉巴拉巴拉…此处省略一万字。
* S! _1 z3 J: a  E! N
8 [* x4 D6 f) x  @$ Q
我绞尽脑汁，仍是不得其解。于是我就去问度娘…
在我看了众多博客之后，终于有了一种拨云见日的感觉，看下图
% ]/ p" T7 c8 ?8 [) {/ n
　　 由第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。

# g) M7 ^! J% w, k( L
至此，算是把求解数组 next 的算法弄清楚了（其实是，终于把 k = next[k] 弄懂了…）
  p! E4 P# G' f' w* b
' b' N/ c6 e) P' |
: t# u9 ^4 n3 z& P4 A$ E因为这个算法神奇难解之处就在k=next[k]这一处的理解上，网上解析的非常之多，有的就是例证，举例子按代码走流程，走出结果了，跟肉眼看的一致，就认为解释了为什么k=next[k]；很少有看到解释的非常清楚的，或者有，但我没有仔细和耐心看下去。我一般扫一眼，就大概知道这个解析是否能说的通。仔细想了三天，搞的千转百折，山重水复，一头雾气缭绕的。搞懂以后又觉得确实简单，但是绕人，烧脑。
( i6 H+ `5 e; [
; I4 Y7 J4 R$ t" z
) ?2 o  p6 C6 a& r& v: f. i再此特别感谢昵称为“sofu6”的博客园主，正是他的博客，让我这愚笨的脑袋瓜开窍了

8 W2 k# a2 I* A( ~) _
& N5 ?$ E. D. E1 {- S6 @KMP算法实现
# z, s1 F7 `, o9 ?- t$ D当你求出了 next 数组之后，KMP 算法就很轻易搞定了，下面我用三张图，让你明白 KMP 算法完成匹配的整个过程。
- J& f* n" U" i0 F8 ?  \以目标串：s，指针为 i ；模式串：t 指针为 j ; 为例
. p" c/ o6 S  s) D8 Y
  {2 K" z& w* L, @3 S' F上图表示：“si-j ~ si-1” == “t 0 ~ t j-1”，s i != t j（前面都相等，但比较到 t j 时发现不相等了）且next[j] == k。

) z" q8 Z( n% W根据 next 数组的定义得知 “t k ~ t j-1” == “t 0 ~ t k-1”，所以 “t 0 ~ t k-1” == “si-k ~ si-1”
9 g  J! X0 j# Z6 I
将模式串右移，得到上图，这样就避免了目标穿的指针回溯。


都明了之后就可以手写 KMP 的代码了
  K& W8 e& m7 W( H0 M
4 A- G$ \) r1 z: Y3 ]5 Q! l
int KMP(String s,String t)
- ?( b% u" i4 I+ W  u  X% q2 I{
5 [: R$ ]: C- S3 L& h   int next[MaxSize],i=0;j=0;
* V- \1 @7 ^8 y0 L1 y' P   Getnext(t,next);
   while(i<s.length&&j<t.length)
   {
3 @+ |- s4 o7 j, h8 Z' `. R      if(j==-1 || s==t[j])
/ V& N& V$ p  {5 I5 Y      {
8 o3 s# j" M( F8 c( b         i++;
" `7 \5 q& h. z" ?* }         j++;
      }
      else j=next[j];               //j回退。。。
! M" b( k3 X8 b, A& b5 a   }
   if(j>=t.length)
% L0 o" T& x# t, k/ O& ~# [       return (i-t.length);         //匹配成功，返回子串的位置
   else
      return (-1);                  //没找到
* v+ _! y+ D6 w}
- e3 g# v0 Y2 W+ \5 C
改进后的 next 求解方法
先来看一下上面算法存在的缺陷：
' z9 x  L- U) V/ S& x
显然，当我们上边的算法得到的next数组应该是[ -1，0，0，1 ]
2 V- l+ I4 Z& G. L+ m
; m; \) B! O1 N, f/ i9 \4 K
所以下一步我们应该是把j移动到第1个元素咯：

不难发现，这一步是完全没有意义的。因为后面的B已经不匹配了，那前面的B也一定是不匹配的，同样的情况其实还发生在第2个元素A上。
  P9 R4 k$ c5 T
# V2 C3 S: t8 z# L
1 C6 ^) K7 J( T+ R显然，发生问题的原因在于t[j] == t[next[j]]。
9 k# m8 e$ Z: R5 H2 {; g

% J! d! d# X9 Q7 x# }# R) w, |所以我们需要谈价一个判断：

) A# @9 U0 F9 M  K+ a" ~& W  X
void Getnext(int next[],String t)
{
. p  r( v$ s, D. A4 T# d   int j=0,k=-1;
   next[0]=-1;
   while(j<t.length-1)
   {
+ {! m5 L& Z8 X1 y% z      if(k == -1 || t[j] == t[k])
1 B/ i6 r% ^9 q8 T; x: S. a4 K5 ^      {
' s* h0 c% b, B& {# J2 ]8 e0 Z         j++;k++;
         if(t[j]==t[k])//当两个字符相同时，就跳过
            next[j] = next[k];
         else
6 K$ F) v/ Z  D$ x" F  q            next[j] = k;
      }
4 o" [0 U9 Q! F  N" a) ?% [      else k = next[k];
# M6 L* }1 p3 [8 G2 C) L* U   }
}
————————————————
+ `, r: R0 t9 x6 F1 G# o版权声明：本文为CSDN博主「June·D」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
* ~1 x( d! q: D0 q9 s( d, m9 u原文链接：https://blog.csdn.net/dark_cy/article/details/88698736

; X9 d) O5 c9 U" p$ Q  t
5 P7 q- H& p+ K' p

1051373629

zanzanzanzanzan
" f6 n6 b: e: E# C