loader
12 May , 2020

KMP算法详解以及KMP算法实现

author

DK丶S CSDN博客

shape animated shape animated shape animated

使用第三方账号注册

使用手机号/邮箱注册

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

提取加速匹配的信息

上面说道 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 }。

加速信息,即数组 next 的提取是整个 KMP 算法中最核心的部分,弄懂了 next 的求解方法,也就弄懂了 KMP 算法的十之七八了,但是不巧的是这部分代码恰恰是最不容易弄懂的……,先上代码

void Getnext(int next[],String t)
{
   int j=0,k=-1;
   next[0]=-1;
   while(j<t.length-1){
      if(k == -1 || t[j] == t[k]){
         j++;k++;
         next[j] = k;
      }
      //此语句是这段代码最反人类的地方,如果你一下子就能看懂,那么请允许我称呼你一声大神!
      else k = next[k];
   }
}

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

1、特殊情况

当 j 的值为 0 或 1 的时候,它们的 k 值都为 0,即 next[0] = 0、next[1] =0。但是为了后面 k 值计算的方便,我们将 next[0] 的值设置成 -1。

2、当 t[j] == t[k] 的情况

举个栗子

KMP算法详解以及KMP算法实现

观察上图可知,当 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。

3、当t[j] != t[k] 的情况

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

我绞尽脑汁,仍是不得其解。于是我就去问度娘…

在我看了众多博客之后,终于有了一种拨云见日的感觉,看下图

KMP算法详解以及KMP算法实现

由第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。

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

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

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

KMP算法实现

当你求出了 next 数组之后,KMP 算法就很轻易搞定了,下面我用三张图,让你明白 KMP 算法完成匹配的整个过程。

以目标串:s,指针为 i ;模式串:t 指针为 j ; 为例

KMP算法详解以及KMP算法实现

上图表示:“si-j ~ si-1” == “t 0 ~ t j-1”,s i != t j(前面都相等,但比较到 t j 时发现不相等了)且next[j] == k。

KMP算法详解以及KMP算法实现

根据 next 数组的定义得知 “t k ~ t j-1” == “t 0 ~ t k-1”,所以 “t 0 ~ t k-1” == “si-k ~ si-1”

KMP算法详解以及KMP算法实现

将模式串右移,得到上图,这样就避免了目标穿的指针回溯。

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

int KMP(String s,String t)
{
   int next[MaxSize],i=0;j=0;
   Getnext(t,next);
   while(i<s.length&&j<t.length)
   {
      if(j==-1 || s[i]==t[j]){
         i++;
         j++;
      }
      else j=next[j];//j回退。。。
   }
   if(j>=t.length)
       return (i-t.length);//匹配成功,返回子串的位置
   else
      return (-1);//没找到
}

改进后的 next 求解方法

先来看一下上面算法存在的缺陷:

KMP算法详解以及KMP算法实现

显然,当我们上边的算法得到的next数组应该是[ -1,0,0,1 ]

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

KMP算法详解以及KMP算法实现

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

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

所以我们需要谈价一个判断:

void Getnext(int next[],String t)
{
   int j=0,k=-1;
   next[0]=-1;
   while(j<t.length-1)
   {
      if(k == -1 || t[j] == t[k])
      {
         j++;k++;
         if(t[j]==t[k])//当两个字符相同时,就跳过
            next[j] = next[k];
         else
            next[j] = k;
      }
      else k = next[k];
   }
}

Robin Binar Themeix

Onubia, turpis inceptos pharetra. Ipsum erat rutrum, luctus non rhoncus quam quisque posuere, eros pede leo facilisis at risus. Ea sit consectetuer suscipit pede hac purus, erat nec

猜你喜欢

WinSxS是什么,C盘WinSxS是什么文件夹?

11 Dec , 2018

2018-12-11 00:01

mac下安装composer,macos系统下全局安装composer

11 Dec , 2018

2018-12-11 00:11

区块链是什么,区块链到底是什么意思,看完这段话就懂了

11 Dec , 2018

2018-12-11 00:19

wireshark使用教程,网络抓包工具wireshark中文版使用教程

11 Dec , 2018

2018-12-11 00:48

VBS整人代码大集合,学会用VBS来编小程序对心仪的女神表白

11 Dec , 2018

2018-12-11 02:06

网友评论 ( 0 条评论 )

评论