求出子串(模式串)的next函数值,利用kmp算法实现模式与主串的匹配算法
来源:百度知道 编辑:UC知道 时间:2024/08/31 03:32:01
一、实验目的
熟悉字符串的使用。
掌握如何用kmp算法实现字符串的模式匹配。
二、实验要求
熟悉C语言编程。
三、实验内容
求出子串(模式串)的next函数值,利用kmp算法实现模式与主串的匹配算法。
四、实验步骤
1.生成模式串的next函数
2.从第1个字符开始,进行模式串与主串的比较,
3.如果出现失配,主串指针不变,将模式串的指针退回到next[j]所指的位置,继续与主串进行比较。
要C语言的源代码,谢谢啊!
熟悉字符串的使用。
掌握如何用kmp算法实现字符串的模式匹配。
二、实验要求
熟悉C语言编程。
三、实验内容
求出子串(模式串)的next函数值,利用kmp算法实现模式与主串的匹配算法。
四、实验步骤
1.生成模式串的next函数
2.从第1个字符开始,进行模式串与主串的比较,
3.如果出现失配,主串指针不变,将模式串的指针退回到next[j]所指的位置,继续与主串进行比较。
要C语言的源代码,谢谢啊!
net jump>ks
nb.zazhong>?jiu
shini+chSeNG_KS
BA
NEXT
END
有两种算法:(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"时。自己好好体会吧
你应该到专业的论坛去发帖,这里一般没人肯解决这样复杂的问题。