[理工] 算法 KMP

楼主: hopward (hopward)   2016-11-23 10:58:08
http://i.imgur.com/epl69Jr.jpg
http://i.imgur.com/VcoQHO6.jpg
http://i.imgur.com/vAsooQv.jpg
想请问一下,根据课本prefix function的pseudo code trace课本给的例子ababaa会得到正确的pi(6),但如果我把例子换成下例
http://i.imgur.com/ClyDgyM.jpg
当我trace到i=6的时候,通过第一个while statement
( k=3 且 P[k+1]=b不等于P[i]=c) 此时k被设为pi(3)=1
接着无法通过if叙述,所以会跳去做最下面的pi[6]=1,但事实上根据我的例子,pi[6]最终的结果应该是0
我想问的事,上述虚拟码会work是否是因为电脑为2进位,所以不是a就是b,不能像我举的例子有其他变量吗
作者: yorunohoshi (夜の星)   2016-11-23 15:24:00
k=pi(3)=1出来后 因为又符合k>0&&P[k+1]!=P[i]所以再进去while一次 此时k=pi(1)=0 接着设定pi(6)=0
楼主: hopward (hopward)   2016-11-23 15:49:00
阿对齁 那是while循环 眼脱了 感谢

Links booklink

Contact Us: admin [ a t ] ucptt.com