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];//此语句是这段代码最反人类的地方,如果你一下子就能看懂,那么请允许我称呼你一声大神!
}
}
ok,下面咱们分三种情况来讲 next 的求解过程
-
特殊情况
当 j 的值为 0 或 1 的时候,它们的 k 值都为 0,即 next[0] = 0、next[1] =0。但是为了后面 k 值计算的方便,我们将 next[0] 的值设置成 -1。 -
当 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。 -
当t[j] != t[k] 的情况
关于这种情况,在代码中的描述就是“简单”的一句 k = next[k];。我当时看了之后,感觉有点蒙,于是就去翻《数据结构教程》。但是这本书里,对于这行代码的解释只有三个字:k 回退…!于是我从“有点蒙”的状态升级到了“很蒙蔽”的状态,我心想,k 回退?我当然知道这是 k 退回,但是它为什么要会退到 next[k] 的位置?为什么不是回退到k-1???巴拉巴拉巴拉…此处省略一万字。
我绞尽脑汁,仍是不得其解。于是我就去问度娘…
在我看了众多博客之后,终于有了一种拨云见日的感觉,看下图
由第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 ; 为例
上图表示:“si-j ~ si-1” == “t 0 ~ t j-1”,s i != t j(前面都相等,但比较到 t j 时发现不相等了)且next[j] == k。
根据 next 数组的定义得知 “t k ~ t j-1” == “t 0 ~ t k-1”,所以 “t 0 ~ t k-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];
}
}
本文对sofu6的博客多有借鉴,所以在此特别鸣谢,并附上他的博客:想看点这里
更多推荐
所有评论(0)