KMP算法,next函数 求教!该如何处理
KMP算法,next函数 求教!!
KMP算法的next函数大致的理论我懂了,不过写出代码就立刻糊涂了
磨呀磨呀磨,最后还是......
已知:next[1] = 0;
假设:next[j] = k; 又str[j] = str[k];
则:next[j+1] = k+1;
若:str[j]!=str[k]则需往前回朔,检查str[j] = str[?];
代码:void get_next(string str,int next[])
{
int i,j;
i = 1; j = 0;
len = sizeof(next)/sizeof(next[0]);
while(i < len)
{
if(j = 0 || str[i] == str[j])
{
++i;++j;
next[i] = j;
}
else j = next[j];
}
}
------解决方案--------------------
看算法导论, 那一章从头理解到尾, 全懂了你也就走出KMP了.
KMP算法的next函数大致的理论我懂了,不过写出代码就立刻糊涂了
磨呀磨呀磨,最后还是......
已知:next[1] = 0;
假设:next[j] = k; 又str[j] = str[k];
则:next[j+1] = k+1;
若:str[j]!=str[k]则需往前回朔,检查str[j] = str[?];
代码:void get_next(string str,int next[])
{
int i,j;
i = 1; j = 0;
len = sizeof(next)/sizeof(next[0]);
while(i < len)
{
if(j = 0 || str[i] == str[j])
{
++i;++j;
next[i] = j;
}
else j = next[j];
}
}
------解决方案--------------------
看算法导论, 那一章从头理解到尾, 全懂了你也就走出KMP了.