KMP算法中next的取值解决思路

KMP算法中next的取值

C/C++ code


void get_next(char *T,int *next)
{
    int i,j;
    i=1;
    j=0;
    next[1]=0;
    while(i<T[0]){               /* T[0]为T的长度 */
        if(j==0||T[i]==T[j]){
            ++i;
            ++j;
            next[i]=j;
        }else
            j=next[j];
    }
}

这个是大话数据结构里面的代码在上面的代码中。为什么j=next[j];这一句不改成j=0;呢/？我测试过许多的字符串好像改成j=0结果也是对的。对KMP的算法到现在都还有点不是很了解。

------解决方案--------------------
j = next[j];算法更快吧。。
http://topic.****.net/u/20120328/20/89df27a0-cc8e-4880-9dc7-448d517d10b7.html
------解决方案--------------------
j=0就让失配时的模式匹配位置回到第一个字符了，但实际情况则不一定该回到那里，回去太多可能造成丢失匹配。

比如模式串：abaabcaca，next应该是 0 1 1 2 2 3 4 1 2，如果用j=0，就会变成0 1 1 2 1 1 2 1 2。当在第6个字符失配时，后一个方案会使得匹配位置回到第一个字符，但实际上这时应该回到第3字符的位置，回到第一字符就可能丢失匹配。
------解决方案--------------------
kmp的精华就在于这个next[j]，你不用这个next，就跟普通的做法没多少区别了

KMP算法中next的取值解决思路

相关推荐