回 帖 发 新 帖 刷新版面

主题:[讨论]KMP算法想不通

kmp 算法  83页  \
void get -next(sstring T,int next[])//求模式串T的next函数值并存入数组next.
{ i=1;next[1]=0;j=0;
while(i<T[0]){
if(j==0||t[i]==t[j]){++i;++j;next[i]=j;}
else j=next[j];
}


J     1 2 3 4 5 6 7 8
模式  a b a a b c a c
next[j]0 1 1 2 2 3 1 2
执行循环!当i=1,j=0 时  ++i ++j  next[2]=1
  此时 i=2 j=1
循环   t[i]不等于t[j]  else  j=next[j]   既 1=next[1]
和条件 next[1]=0 矛盾 很迷惑。
如果 t[i]一直不等于t[j]  那会一直执行else j=next[j]  那样是死循环吧!
大家给点思路。

回复列表 (共2个回复)

沙发

j=next[j];
是一个赋值语句,是把next[j]的值赋给j
若j=1 
执行完 j =next[1]
后 j=0
你可以加个输出语句看看
而且不是死循环

板凳

http://hi.baidu.com/strainboy/blog/item/a3abf3fd5dcc281208244d7b.html
给个例子 俺写的 ..大虾就别看了

我来回复

您尚未登录,请登录后再回复。点此登录或注册