主题:[讨论]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] 那样是死循环吧!
大家给点思路。
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] 那样是死循环吧!
大家给点思路。