求助!——>数据结构 KMP-next[j]问题
已知模式串='ababaabab', 则next[j]=______。
实际上是有个诀窍的,说白了很简单
就以
a b a b a a b a b
0 1 1 2 3 4 2 3 4
为例
next[j] 里面 开头的红色01 没什么好说的,固定格式.
我就以兰色的4 来说明下为什么是4.
与4有关的, 是4所对应的兰色a之前的所有的字符,即紫色的 a b a b a
这个字符串中所有符合匹配条件的字符串如下
a b a b a a b a b a
a a
a b a a b a 最长的匹配字符串(a b a b a本身除外)在这里 ,长度为3, 再加上1,就是4了
注意next[ j ]中4 的位置! 至于为什么要加1 ,大家自己去思考吧, 明白了为什么要加1,KMP算法也就自然明白了
next[ j ]中其他位置的数值也可以用同样的方法得出
再找几个例子用这个方法试下吧, 绝对百试百灵
[此贴子已经被作者于2006-4-27 15:56:42编辑过]