+ -
当前位置:首页 → 问答吧 → 请教 关于KMP算法中的next数组的求法

请教 关于KMP算法中的next数组的求法

时间:2011-09-02

来源:互联网

C/C++ code
void GetNext(SString S, int *next)
{
    int i, j;
    i = 1;
    j = 0;            //为什么初值是这样设置
    next[1] = 0;

    while (i<T[0])
    {
        if (j==0 || T[i]==T[j])        //什么时候j==0
        {
            ++i;
            ++j;
            next[i] = j;
        }
        else
            j = next[j];            //这句更不明白了。。
    }
}
KMP算法我懂了 next数组我自己在纸上也能求出来,可是就是这个函数不明白, 谁能帮我

作者: zhuyi2654715   发布时间: 2011-09-02

引用楼主 zhuyi2654715 的回复:
KMP算法我懂了 next数组我自己在纸上也能求出来,可是就是这个函数不明白, 谁能帮我

貌似你还不懂KMP。
//什么时候j==0
第一次进while的时候j不就是0么。
不知道你是语言不行还是算法不行

作者: maoxing63570   发布时间: 2011-09-02

LZ .你去看严蔚敏网上的KNP算法视频。我这几天看了三遍。。。。终于有点头绪了。她讲的实在太好了。想不懂都难。。。。你就百度搜索严蔚敏KMP算法。。你会懂了的

作者: justlovetao   发布时间: 2011-09-02

昨天晚上迷迷糊糊就发了
现在我就这句不明白
 j = next[j]; 
能帮我解释一下吗?

作者: zhuyi2654715   发布时间: 2011-09-02