KMP算法—终于全部弄懂了

杨利霞

KMP算法—终于全部弄懂了
简介
+ `2 j; [0 _/ E( J, D! l6 e8 [　　KMP 算法是 D.E.Knuth、J,H,Morris 和 V.R.Pratt 三位神人共同提出的，称之为 Knuth-Morria-Pratt 算法，简称 KMP 算法。该算法相对于 Brute-Force（暴力）算法有比较大的改进，主要是消除了主串指针的回溯，从而使算法效率有了某种程度的提高。
, K4 D  Z6 _1 n$ ^+ p. Y7 w

* A! B4 g9 Y: ~" _+ e# X5 W$ L提取加速匹配的信息
6 A5 D  o) ~& G* Z& u; v  u* ?　　上面说道 KMP 算法主要是通过消除主串指针的回溯来提高匹配的效率的，那么，它是则呢样来消除回溯的呢？就是因为它提取并运用了加速匹配的信息！
* f* r, }% m6 h2 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 }。
  |- `1 H0 K7 K, U　　
) j0 f. U1 P! p& u9 _6 w3 h' Q& f　　加速信息，即数组 next 的提取是整个 KMP 算法中最核心的部分，弄懂了 next 的求解方法，也就弄懂了 KMP 算法的十之七八了，但是不巧的是这部分代码恰恰是最不容易弄懂的……
　　
先上代码
0 L" o! D6 F) ]1 l
0 d* {5 `" s  `3 J
0 \6 {" S0 g  K' U# [void Getnext(int next[],String t)
: r: W; w1 q1 o8 \" S) u4 {{
; n2 G2 j# e! K# f   int j=0,k=-1;
   next[0]=-1;
9 u! X8 ~9 C& m5 Q+ _0 Z   while(j<t.length-1)
4 |. J9 p( U2 v  d   {
      if(k == -1 || t[j] == t[k])
      {
3 D# q1 o2 I) j- K, v         j++;k++;
) s9 ~; ~8 p) _$ t5 U         next[j] = k;
9 K& ]1 d* ]' L% |6 G  k      }
8 m5 U6 {- ?. @4 |7 U+ ]) b6 g/ j      else k = next[k];//此语句是这段代码最反人类的地方，如果你一下子就能看懂，那么请允许我称呼你一声大神！
6 j# ?, P" Q5 T( v   }
0 o  O9 Z9 H6 x( G6 R}
+ S8 y) X- D/ T5 \5 O
4 r! m# v+ e; _  \ok，下面咱们分三种情况来讲 next 的求解过程
& R* \3 n( M, E# f- z
" @* F# L- P5 {' t1 r( R6 ]
; d( z7 A2 R1 ?6 H" q特殊情况
- A* F* A4 ~: E  P: k3 \/ j; i0 H当 j 的值为 0 或 1 的时候，它们的 k 值都为 0，即 next[0] = 0、next[1] =0。但是为了后面 k 值计算的方便，我们将 next[0] 的值设置成 -1。


当 t[j] == t[k] 的情况
举个栗子
2 Z( A! D$ C( X/ i- t, s+ z9 q
观察上图可知，当 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 Z# S9 t! Z  \, q" _+ g
- u: K# V2 z# R: W! e! ?
) v/ n8 p" V4 h5 E  s当t[j] != t[k] 的情况
关于这种情况，在代码中的描述就是“简单”的一句 k = next[k]；。我当时看了之后，感觉有点蒙，于是就去翻《数据结构教程》。但是这本书里，对于这行代码的解释只有三个字：k 回退…！于是我从“有点蒙”的状态升级到了“很蒙蔽”的状态，我心想，k 回退？我当然知道这是 k 退回，但是它为什么要会退到 next[k] 的位置？为什么不是回退到k-1？？？巴拉巴拉巴拉…此处省略一万字。

2 H' K, _0 Z! V9 f# q. Y, G4 }
我绞尽脑汁，仍是不得其解。于是我就去问度娘…
; }7 ]0 j& Q; W" j在我看了众多博客之后，终于有了一种拨云见日的感觉，看下图

　　 由第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% L6 C' X9 A7 C) I$ \2 M9 s

( n/ f( Z" }  f至此，算是把求解数组 next 的算法弄清楚了（其实是，终于把 k = next[k] 弄懂了…）

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

" g+ F: X3 Y  S4 L2 U
; L' B6 ], B& z3 {再此特别感谢昵称为“sofu6”的博客园主，正是他的博客，让我这愚笨的脑袋瓜开窍了
; C3 f1 p0 t; Y& B4 {
4 |3 y) Y1 ]/ @1 h
KMP算法实现
当你求出了 next 数组之后，KMP 算法就很轻易搞定了，下面我用三张图，让你明白 KMP 算法完成匹配的整个过程。
5 x! e: u  [  k  @3 m, M" ^4 v以目标串：s，指针为 i ；模式串：t 指针为 j ; 为例
& j9 c' h# t* a5 Y* z9 {! n
上图表示：“si-j ~ si-1” == “t 0 ~ t j-1”，s i != t j（前面都相等，但比较到 t j 时发现不相等了）且next[j] == k。

2 `: \/ Q8 K9 }8 g. r根据 next 数组的定义得知 “t k ~ t j-1” == “t 0 ~ t k-1”，所以 “t 0 ~ t k-1” == “si-k ~ si-1”
& h% ?% ^( |& ?& Z- J" Z  y
将模式串右移，得到上图，这样就避免了目标穿的指针回溯。

+ Z8 E: R/ ^" m  q2 c3 c
3 k" U& O0 `4 v4 I都明了之后就可以手写 KMP 的代码了


int KMP(String s,String t)
% Q/ |9 o2 X) [- B# ]1 }& s{
   int next[MaxSize],i=0;j=0;
- D3 J0 \, l. R. [9 Z6 g" x   Getnext(t,next);
   while(i<s.length&&j<t.length)
   {
      if(j==-1 || s==t[j])
& T/ w, ^2 C0 Y+ A4 Q* _& v      {
. K) P) V! e' n- L% r         i++;
         j++;
5 N0 [) k5 x& w  a! Z2 ?" U! z. I      }
& y, r3 m0 ]! o% l) ~% m, A      else j=next[j];               //j回退。。。
$ U1 L7 y+ {) y9 [1 F; q, h   }
. C: x- n8 h4 Z   if(j>=t.length)
" O- M3 Q- G! h: j/ W       return (i-t.length);         //匹配成功，返回子串的位置
   else
      return (-1);                  //没找到
}

改进后的 next 求解方法
先来看一下上面算法存在的缺陷：
' i. g% |- G2 D  E) Z9 ?5 c) Q3 [
显然，当我们上边的算法得到的next数组应该是[ -1，0，0，1 ]

$ u4 u+ G0 Z$ v9 ?6 K& W
1 \6 e( i1 Y+ b% B% r9 O5 r3 r+ U所以下一步我们应该是把j移动到第1个元素咯：
1 O, v. f( u, j" W1 V' t
9 p* d& C8 @/ m* [6 a不难发现，这一步是完全没有意义的。因为后面的B已经不匹配了，那前面的B也一定是不匹配的，同样的情况其实还发生在第2个元素A上。
% a; S& X% u0 Q, T# k1 c8 s+ Q1 R; [
  e1 P; X5 b. @+ Q/ x) R/ Q9 p
显然，发生问题的原因在于t[j] == t[next[j]]。
6 b7 C' u( {# u) w; \: ~
1 Y! i6 ~) J6 \; h5 o) H
所以我们需要谈价一个判断：
9 i9 g  [. w  A/ r, _2 r! p
1 n) i! r. ~) w
8 k! J5 D) T8 C5 y' g& Ivoid Getnext(int next[],String t)
, s+ l6 p; f9 N5 z2 k1 ]' v{
$ ^, S" l, w, w4 {8 T$ v0 R   int j=0,k=-1;
   next[0]=-1;
   while(j<t.length-1)
   {
5 @8 K5 Z* r6 r& M' Q4 v. e5 v      if(k == -1 || t[j] == t[k])
' p5 T# ]2 ]& |: }! @: m7 g      {
         j++;k++;
' R2 Y$ n/ I8 {         if(t[j]==t[k])//当两个字符相同时，就跳过
& }1 }2 M9 J4 N$ L  W  J2 O6 k            next[j] = next[k];
         else
            next[j] = k;
      }
      else k = next[k];
   }
}
————————————————
版权声明：本文为CSDN博主「June·D」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
, S" O3 ^8 ^5 Z1 k" p/ J原文链接：https://blog.csdn.net/dark_cy/article/details/88698736
+ R0 F) F7 Z* I( z5 O
  w5 P+ }  d6 _$ ]- l6 Z9 t
& ~' R% U. V- t- S5 [* _

1051373629

zanzanzanzanzan