首页 > 搞懂KMP算法,真不容易
头像
linux地平线
编辑于 2021-08-20 17:04
+ 关注

搞懂KMP算法,真不容易

简介

  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];//如果你一下子就能看懂,那么请允许我称呼你一声大神!
   }
}

下面分三种情况来讲 next 的求解过程

1. 特殊情况

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

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

举个例子
图片说明

观察上图可知,当 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 回退…!查看了众多博客之后,终于拨云见日。看下图
图片说明

由第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];很少有看到解释的非常清楚的,或者有,但我没有仔细和耐心看下去。我一般扫一眼,就大概知道这个解析是否能说的通。仔细想了三天,搞的千转百折,山重水复,一头雾气缭绕的。搞懂以后又觉得确实简单,但是绕人,烧脑。

KMP算法实现

当你求出了 next 数组之后,KMP 算法就很轻易搞定了,下面我用三张图,让你明白 KMP 算法完成匹配的整个过程。
以目标串:s,指针为 i ;模式串:t 指针为 j ; 为例
图片说明

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

根据 next 数组的定义得知 “tk~ tj-1” == “t0~ tk-1”,所以 “t0~ tk-1” == “si-k~ si-1”
图片说明

将模式串右移,得到上图,这样就避免了目标穿的指针回溯。
都明了之后就可以手写 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 求解方法

先来看一下上面算法存在的缺陷:
图片说明

显然,当我们上边的算法得到的next数组应该是[ -1,0,0,1 ]
所以下一步我们应该是把j移动到第1个元素咯:
图片说明

不难发现,这一步是完全没有意义的。因为后面的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];
   }
}

最后看KMP算法完整代码,可直接拷贝运行
KMP算法源码

全部评论

(2) 回帖
加载中...
话题 回帖