楼主

[请教] 有关KMP算法 是不是有个KMP算法的改进版，模板向量从-1开始算的？ 请教，谢谢！    收藏   分享   顶(0)    关闭广告显示

----------------------------------------------
一只小动物。。。

	第2楼

是的，有这个版本，模板向量从-1开始算的。

	第3楼

能不能详细说说？

----------------------------------------------
一只小动物。。。

	第4楼

课本上的求法是: N[i]= max{k| P1P1....Pk=Pi-k+1....Pi-1Pi}  也就是P1P2....Pi最长首尾真子串的长度         0   i=0 02年的课件上: N[i]= max{k| P1P1....Pk=Pi-k....Pi-1Pi-1}  也就是P1P2....Pi-1最长首尾真子串的长度         0   其他情况         -1  i=0 所谓的改进是： 当Pi=Pk时 N[i]=N[k];具体的看下02年课件的算法吧 举个例子：          a  b  c  a  a  b  a  b  c          0  0  0  1  1 2  1  2 3         -1  0  0  0  1 1  2  1 2 改进: -1  0  0  -1 1 0  2  0 0

	第5楼

这是C++殷人昆书中的方法吧？ 我个人更喜欢严蔚敏版中从0开始的方法。 感觉要直观些。这个-1搞得有点恶心。

----------------------------------------------
长江后浪，无坚不摧。