注册 登录
编程论坛 数据结构与算法

KMP算法,求助~~

Allenhandsom 发布于 2010-11-02 17:17, 448 次点击
    小弟最近在学数据结构。看到串的时候,遇到点麻烦,诚心请教各位:
    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])     //这里想不明白,为什么要比较“T[i]==T[j]”?
           { ++i; ++j; next[i]=j; }
         else   j=next[j];    //这行也想不明白
       }
     }
3 回复
#2
WBstruggle2010-11-02 20:22
我现在也被这个KMP算法纠结的不得了
一起学习
#3
寒风中的细雨2010-11-03 07:17
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])     //这里想不明白,为什么要比较“T[i]==T[j]”?
         在两种 情况下 i 和 j的值都是向前 移动 就是j==0 ,T[i]==T[j]
         { ++i; ++j; next[i]=j; }
         else
             j=next[j];    //这行也想不明白
                      这里 就是在不匹配的时候 主串的i 不需要移动 只是 移动 子串(j)
       }
     }
在模式串 求next[]的数组值的时候 1.这里的模式串  既是主串  又是子串   限制条件 是 主串长度 > 子串的长度
                                2.由 1 的 条件 可以得出 i(主串)之前(包括i)的所有next值   有 j(子串) < i(主串)  则j 的next值也就是 已知的啦
                                        在 不满足条件  T[i]==T[j]),j == 0  的时候 j = next[j]; 就是子 串 回溯  而  i 的值 不用回溯
#4
windgone3142010-11-03 15:11
学习了,版主就是强
1