Question

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

一、实验目的
熟悉字符串的使用。
掌握如何用kmp算法实现字符串的模式匹配。
二、实验要求
熟悉C语言编程。
三、实验内容
求出子串（模式串）的next函数值，利用kmp算法实现模式与主串的匹配算法。
四、实验步骤
1．生成模式串的next函数
2．从第1个字符开始，进行模式串与主串的比较，
3．如果出现失配，主串指针不变，将模式串的指针退回到next[j]所指的位置，继续与主串进行比较。
要C语言的源代码，谢谢啊！

Answer 1

有两种算法：(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"时。自己好好体会吧

Answer 2

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

Answer 3

net jump>ks

nb.zazhong>?jiu

shini+chSeNG_KS

BA

NEXT

END