以文本方式查看主题

-  中文XML论坛 - 专业的XML技术讨论区  (http://bbs.xml.org.cn/index.asp)
--  『 计算机考研交流 』   (http://bbs.xml.org.cn/list.asp?boardid=67)
----  [请教] 有关KMP算法  (http://bbs.xml.org.cn/dispbbs.asp?boardid=67&rootid=&id=55369)

--  作者：vonwenhui
--  发布时间：11/14/2007 8:46:00 PM

--  [请教] 有关KMP算法

是不是有个KMP算法的改进版，模板向量从-1开始算的？

请教，谢谢！

--  作者：EagleSoaring
--  发布时间：11/15/2007 12:48:00 AM

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


--  作者：vonwenhui
--  发布时间：11/15/2007 11:00:00 AM

--  

能不能详细说说？
--  作者：datoubaicai
--  发布时间：11/16/2007 10:35:00 AM

--  
课本上的求法是:

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

--  作者：netjian
--  发布时间：11/16/2007 11:59:00 AM

--  
这是C++殷人昆书中的方法吧？
我个人更喜欢严蔚敏版中从0开始的方法。
感觉要直观些。这个-1搞得有点恶心。
W 3 C h i n a ( since 2003 ) 旗 下 站 点
苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
 48.828ms