请教一KMP算法的问题

leon57 发布于 2008-10-25 21:49， 1010 次点击

int Index_KMP(HString &S,HString &T,int pos)
{
    i=pos;
    j=1;
    while(i<=S.len&&j<=T.len)
    {
        if(S.ch[i]==T.ch[j])
        {
            ++i;
            ++j;
        }
        else j=next[j];
    }
    if(j>T.len) return i-T.len;
    else return 0;
}

里面的next[j]怎么编写?

1 回复

惜缘03102012-11-18 21:58

get_next(struct string T,int next[])
{
    int j,k;
    j=0,k=-1;
    next[1]=-1;
    while(j<T.length)
    {
        if(k==-1||T.str[j]==T.str[k])
       {j++;k++;next[j]=k;}
       else{k=next[k];}
       }
    }