问下严蔚敏数据结构的串
里面一章说的模式匹配的改进算法给出的例子是这样的
j |1 2 3 4 5 6 7 8
模式| ab a a b c a c
next | 011 2 2 3 1 2
next 是先赋0值的.
之后给出了求 next值的函数
如下所示;
void get_next(SString T,int &next[])
{
//求模式串T的next函数值并存入数组next
i = 1;next = 0;j = 0;
while(i<T) //T这里应该是指串T的长度
{
if(j==0 || T == T)
{
++i;++j;
next = j;
}
else
j = next;
}
}
不过按这个算法,得到的 next的值, 到了 next 就不对了,
按上面的例子到了 next 应该是等于 2,但按这算法是等于1
请问这是怎么回事呢? 没看过这本书,数据结构方面的东西,看着就头大.... 看了她的视频还是一样的算法,但算出来确实不对.... KMP,建议G搜索,印象有
直接说明,恐用词晦涩,反而误导 百度百科搜索KMP算法,那里的讲解比较详细 = =
页:
[1]