求出子串（模式串）的next函数值，利用kmp算法实现模式与主串的匹配算法

发布网友发布时间：2022-04-18 14:24

共3个回答

热心网友时间：2022-04-18 15:53

有两种算法：(len为模式串长度,T[]为模式串)
1、i = 1; j = 0; next[1] = 0;
while(i<len)
{
if((j == 0)||(T[i] == T[j]))
{
i++; j++;
next[i] = j;
}
else
j = next[i];
}

2、i = 1; j = 0; next[1] = 0;
while(i<len)
{
if((j == 0)||(T[i] == T[j]))
{
i++; j++;
if(T[i] != T[j])
next[i] = j;
else
next[i] = next[j];
}
else
j = next[i];
}
总的来说第二种方法相对于第一种方法有改进，因为第一种方法在一些情况下有缺陷，如模式串为"aaaab"时。自己好好体会吧

热心网友时间：2022-04-18 17:11

你应该到专业的论坛去发帖,这里一般没人肯解决这样复杂的问题。

热心网友时间：2022-04-18 18:46

net jump>ks

nb.zazhong>?jiu

shini+chSeNG_KS

BA

NEXT

END