KMP算法—终于全部弄懂了

杨利霞

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

- D. N2 w- u+ K9 A# H% t% ^$ S5 X
  U- j& w3 ?: z0 X9 Q, L; k提取加速匹配的信息
! }! B: a0 P" ^% R: Z* K　　上面说道 KMP 算法主要是通过消除主串指针的回溯来提高匹配的效率的，那么，它是则呢样来消除回溯的呢？就是因为它提取并运用了加速匹配的信息！
6 z4 X! _% q4 p3 O) E: Q7 R6 o# 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 }。
　　
( @2 e6 C* P, E# Z3 n  z　　加速信息，即数组 next 的提取是整个 KMP 算法中最核心的部分，弄懂了 next 的求解方法，也就弄懂了 KMP 算法的十之七八了，但是不巧的是这部分代码恰恰是最不容易弄懂的……
" C& `$ o* |+ s. Y8 D　　
0 G  \. y  V9 `5 @# V( d, ~先上代码
- J( _* K% l# w/ V4 w
- m1 {  B/ b# Y+ F
2 J! g" r1 l7 t  m8 qvoid Getnext(int next[],String t)
+ k! d; ^( a4 r{
7 K7 s4 @1 b0 \5 W; H4 s: l   int j=0,k=-1;
+ V2 \+ I" ^3 Y   next[0]=-1;
   while(j<t.length-1)
   {
0 F3 B, O; p+ Z( z4 P      if(k == -1 || t[j] == t[k])
3 E/ C0 B  X9 a  c      {
6 Y# y5 ~+ H# ]4 r, W0 f  K. W         j++;k++;
         next[j] = k;
8 I/ n( M" A2 B, b/ d      }
8 |  g  c  A: b1 @; x2 p& [      else k = next[k];//此语句是这段代码最反人类的地方，如果你一下子就能看懂，那么请允许我称呼你一声大神！
   }
}
! S1 N9 ^6 X9 w$ h. w5 N: Y8 U( a
ok，下面咱们分三种情况来讲 next 的求解过程
7 X% I8 l2 }' A# q" T2 Z
1 j: h& E+ Z$ s# ^
) x* f" o: p; i3 ?. [特殊情况
当 j 的值为 0 或 1 的时候，它们的 k 值都为 0，即 next[0] = 0、next[1] =0。但是为了后面 k 值计算的方便，我们将 next[0] 的值设置成 -1。
- P( w+ [' }, w  P/ G

当 t[j] == t[k] 的情况
. b2 s' c, |2 @2 R8 P0 ~& g举个栗子

4 E7 ~+ c& b5 n; U- M1 t观察上图可知，当 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。
" ?% d1 O. @0 }0 f' J8 D# @: g- R

当t[j] != t[k] 的情况
9 H2 ?/ D' d1 a$ ^& V/ Q$ J8 E! k$ x$ o关于这种情况，在代码中的描述就是“简单”的一句 k = next[k]；。我当时看了之后，感觉有点蒙，于是就去翻《数据结构教程》。但是这本书里，对于这行代码的解释只有三个字：k 回退…！于是我从“有点蒙”的状态升级到了“很蒙蔽”的状态，我心想，k 回退？我当然知道这是 k 退回，但是它为什么要会退到 next[k] 的位置？为什么不是回退到k-1？？？巴拉巴拉巴拉…此处省略一万字。
/ Q0 Z; m0 ~4 t( K) A
- u' [/ S6 q5 U7 G8 C
我绞尽脑汁，仍是不得其解。于是我就去问度娘…
( T/ k# N% }% J" Q7 G在我看了众多博客之后，终于有了一种拨云见日的感觉，看下图
6 a& L* E: _; M' s3 \; k
/ j9 \! ?2 P: V7 U, E  d) u; P/ j3 T　　 由第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。
  Y0 B8 ]# }5 Q' m9 N% T; R

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

- ]! k6 n/ J& T2 F- L4 c* H
% c. e6 l7 f+ [3 L4 a) {. A. D- ]因为这个算法神奇难解之处就在k=next[k]这一处的理解上，网上解析的非常之多，有的就是例证，举例子按代码走流程，走出结果了，跟肉眼看的一致，就认为解释了为什么k=next[k]；很少有看到解释的非常清楚的，或者有，但我没有仔细和耐心看下去。我一般扫一眼，就大概知道这个解析是否能说的通。仔细想了三天，搞的千转百折，山重水复，一头雾气缭绕的。搞懂以后又觉得确实简单，但是绕人，烧脑。

( ?  b( w9 o8 I$ y
再此特别感谢昵称为“sofu6”的博客园主，正是他的博客，让我这愚笨的脑袋瓜开窍了
8 k# ^0 S# U; p$ y) e# ^. v% Z% j

KMP算法实现
% f- [) {: M& r* ^! v1 @当你求出了 next 数组之后，KMP 算法就很轻易搞定了，下面我用三张图，让你明白 KMP 算法完成匹配的整个过程。
! \, i4 h) a4 Q$ T4 C4 b以目标串：s，指针为 i ；模式串：t 指针为 j ; 为例
+ N9 N; A6 U) U
上图表示：“si-j ~ si-1” == “t 0 ~ t j-1”，s i != t j（前面都相等，但比较到 t j 时发现不相等了）且next[j] == k。

. o; W: t7 B0 M根据 next 数组的定义得知 “t k ~ t j-1” == “t 0 ~ t k-1”，所以 “t 0 ~ t k-1” == “si-k ~ si-1”

将模式串右移，得到上图，这样就避免了目标穿的指针回溯。
- D" l) D  _+ Z9 g

都明了之后就可以手写 KMP 的代码了

! X: K, k' |; x: A9 u: L
int KMP(String s,String t)
{
5 b% ]' Q8 w( z/ _0 H' r   int next[MaxSize],i=0;j=0;
1 R) g5 M$ x- E- U1 D/ t   Getnext(t,next);
+ ]7 o; @/ Z. m1 X7 M4 i1 @   while(i<s.length&&j<t.length)
8 V5 S1 P' S9 e, n   {
+ Z6 x( a3 ~; m      if(j==-1 || s==t[j])
! G( z9 w! q; Z, A# v( q      {
         i++;
         j++;
      }
' i3 g; k) r. o$ n3 H' Z% J      else j=next[j];               //j回退。。。
/ r! N) e. i1 K( D* f( R3 v. k0 \/ B   }
; R$ {6 m6 |& }   if(j>=t.length)
       return (i-t.length);         //匹配成功，返回子串的位置
7 q6 i7 v/ b+ J- ~7 m* r4 u  w   else
      return (-1);                  //没找到
* Z( v7 }8 x( T3 \0 z. b}

改进后的 next 求解方法
( T& V# A5 Z  s! ]先来看一下上面算法存在的缺陷：
6 o% }; X: e! n& {5 q
% K0 M' D2 `, v& n5 k显然，当我们上边的算法得到的next数组应该是[ -1，0，0，1 ]
& w  B6 d4 n' `8 B% y. i

所以下一步我们应该是把j移动到第1个元素咯：

不难发现，这一步是完全没有意义的。因为后面的B已经不匹配了，那前面的B也一定是不匹配的，同样的情况其实还发生在第2个元素A上。
3 w: r3 w6 E6 ~# q& ]

显然，发生问题的原因在于t[j] == t[next[j]]。


) e8 q, N6 a3 C6 k  G0 t. V所以我们需要谈价一个判断：
6 O) Q$ @6 u) M. u
% z, ]& z  r1 u* }
; P  `; n* ]1 d1 t7 h! |! E. j7 a' Mvoid Getnext(int next[],String t)
! t1 v7 i$ D. ^7 W{
   int j=0,k=-1;
   next[0]=-1;
5 j  c$ r4 r8 V* Y# b. ?   while(j<t.length-1)
+ h5 E8 u1 @+ E1 }   {
      if(k == -1 || t[j] == t[k])
: f, U! t8 f6 Y+ O- G1 K- c/ X      {
         j++;k++;
         if(t[j]==t[k])//当两个字符相同时，就跳过
            next[j] = next[k];
         else
  Q( n: m& d$ ]7 T' U            next[j] = k;
# P- F* k) S* `2 g" N4 [% e9 C      }
      else k = next[k];
   }
3 s- N) b7 d. r1 D}
————————————————
版权声明：本文为CSDN博主「June·D」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/dark_cy/article/details/88698736
6 ?, M/ S# |) U9 A, P6 i( N1 [

$ O' \; N4 I$ k, N

1051373629

zanzanzanzanzan