KMP算法之从next[]到nextVal[] (转)

前些日子写了一篇KMP算法的博文,浅谈数据结构之KMP(串中的模式匹配算法),在这片文章中,谈到了一个模式串K值的记录数组

next[],详细可看那篇文章,其实,前面定义的next[]数组是有一定缺陷的,下面我面我将针对一种情况进行举例:

KMP算法之从next[]到nextVal[] (转)

如上图,如果按照之前的方法所获取的next[]数组的话,当两个字符串匹配到上图的情况是,将会出现如下图的情况:

KMP算法之从next[]到nextVal[] (转)

我们发现,从step1到step3所走的路都是浪费的,因为都是用同一个字母(a)和b去比,而这个计算机也是哼容易识别的,所以对于

next[]的改进是行的通的。

究其原因,为什么我会说上面的3个步骤是白走的呢,以为这是三个连续的相等的a,因此我们可以从第一步直接跳到第四步,即:得到的数组next[j] = k,而模式串p[j] = p[k],当主串中的s[i] 和 p[j] 匹配失败时,不需要再和p[k]比较,而直接和p[next[k]]进行比较,当然可以一直迭代往前。

即:

KMP算法之从next[]到nextVal[] (转)

代码如下:

KMP算法之从next[]到nextVal[] (转)
void get_nextVal(SString T, int nextVal[])
{
int i = 1, j = 0;
nextVal[1] = 0; while( i <= T[0])
{
if(j == 0 || T[i] == T[j])
{
j++;
i++;
if(nextVal[i] == nextVal[j])
{
nextVal[i] = nextVal[j];
}
else
{
nextVal[i] == j;
} }
else
{
j = nextVal[j];
}
} }
KMP算法之从next[]到nextVal[] (转)

注意,所求的永远是前一个的K(写给自己的)嘻嘻~~~~~~

use some of my own time, creativity, energy and talent to help people.
http://www.cnblogs.com/Frank-C/p/4909036.html
上一篇:Linux LVM使用小记


下一篇:Ubuntu 14.04 LTS 安装Docker