UC知道数据结构kmp算法中的next函数
来源：百度知道 编辑：UC知道 时间：2024/06/27 15:48:44
kmp算法中next函数具体是怎样实现的，最好能举例分布说明
kmp策略：调整子串T的位置j，使得S[i-j+1,......i]与T[1,2,....j]保持匹配且新的S[i+1]与T[j+1]恰好匹配,否则j回移或移动i(使得S[i]=T[1]).直至j=T.length.匹配完成.
kmp算法的的流程大致理解了，但是关于next函数的求解，串的每个字符他的next[j]是如何计算出来的。以及他的优化算法nextavl的运行过程不是很懂，那位高手知道的可以解释一下.
void get_next(SString T,int next[])
{ i=1; next[1]=0; j=0;
while(i<T[0])
{
if(j==0||T[i]==T[j])
{ ++i;++j;next[i]=j }
else j=next[j];
}
}
void get_nextval(SString T,int nextavl[])
{
i=1; nextavl[1]=0; j=0;
while(i<T[0])
{
if(j==0||T[i]=T[j])
{
++i; ++j;
if(T[i]!=T[j])
nextavl[i]=j;
else nextval[i]=nextval[j];
}
else j=nextval[j];
}
}
（例：）下面为串aaaab的next计算值
j 1 2 3 4 5
T[] a a a a b
next[j] 0 1 2 3 4
nextval[j] 0 0 0 0 4
kmp策略：调整子串T的位置j，使得S[i-j+1,......i]与T[1,2,....j]保持匹配且新的S[i+1]与T[j+1]恰好匹配,否则j回移或移动i(使得S[i]=T[1]).直至j=T.length.匹配完成.
kmp算法的的流程大致理解了，但是关于next函数的求解，串的每个字符他的next[j]是如何计算出来的。以及他的优化算法nextavl的运行过程不是很懂，那位高手知道的可以解释一下.
void get_next(SString T,int next[])
{ i=1; next[1]=0; j=0;
while(i<T[0])
{
if(j==0||T[i]==T[j])
{ ++i;++j;next[i]=j }
else j=next[j];
}
}
void get_nextval(SString T,int nextavl[])
{
i=1; nextavl[1]=0; j=0;
while(i<T[0])
{
if(j==0||T[i]=T[j])
{
++i; ++j;
if(T[i]!=T[j])
nextavl[i]=j;
else nextval[i]=nextval[j];
}
else j=nextval[j];
}
}
（例：）下面为串aaaab的next计算值
j 1 2 3 4 5
T[] a a a a b
next[j] 0 1 2 3 4
nextval[j] 0 0 0 0 4
我只晓得next
我想你还是不太了解KMP（其实我也不算很懂，尽量说吧O(∩_∩)O~交流下）
那个next其实是T串（字串）自己和自己匹配所得到的。
方法和S T匹配时一样，主不过以前是遇到不匹配时回到NEXT【j】，这个函数中则是遇到不匹配记录下不匹配的位置(说明前面得j个是后面串的后缀)。
至于您说的那个
tvalnext
我不清楚，你能发过来么？一起学习下。O(∩_∩)O~