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.csdn.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，就跟普通的做法没多少区别了

查看更多 下一篇