串匹配BM算法KMP算法BF算法.docx
《串匹配BM算法KMP算法BF算法.docx》由会员分享，可在线阅读，更多相关《串匹配BM算法KMP算法BF算法.docx（10页珍藏版）》请在冰点文库上搜索。
串匹配BM算法KMP算法BF算法
实验报告一串匹配问题
班级：
_计算机师_学号：
2姓名：
_
一、实验题目：
给定一个文本,在该文本中查找并定位任意给定字符串。
2、实验目的：
（1）深刻理解并掌握蛮力法的设计思想;
（2）提高应用蛮力法设计算法的技能;
（3）理解这样一个观点:
用蛮力法设计的算法,一般来说,经过适度的努力后,都可以对算法的第一个版本进行一定程度的改良,改进其时间性能。
三、实验要求：
（1）实现BF算法;
（2）实现BF算法的改进算法:
KMP算法和BM算法;
（3）对上述3个算法进行时间复杂性分析,并设计实验程序验证分析结果。
4、算法描述（对算法主要部分进行伪代码描述或画出流程图）
BF算法：
基本思想：
从主串S的第一个字符开始和模式T的第一个字符进行比较，若相等，则继续比较两者的后续字符；若不相等，则从主串S的第二个字符开始和模式T的第一个字符进行比较，重复上述过程，若T中的字符全部比较完毕，则说明本趟匹配成功；若最后一轮匹配的起始位置是n-m，则主串S中剩下的字符不足够匹配整个模式T，匹配失败。
这个算法称为朴素的模式匹配算法，简称BF算法。
KMP算法：
基本思想：
1.在串S和串T中分别设比较的起始下标i和j；
2.循环直到S中所剩字符长度小于T的长度或T中所有字符均比较完毕
2.1如果S[i]=T[j]，则继续比较S和T的下一个字符；否则
2.2将j向右滑动到next[j]位置，即j=next[j]；
2.3如果j=0，则将i和j分别加1，准备下一趟比较；
2.4如果T中所有字符均比较完毕，则返回匹配的起始下标；否则返回0；
BM算法：
基本思想：
BM算法与KMP算法的主要区别是匹配操作的方向不同。
虽然BM算法仅把匹配操作的字符比突顺序改为从右向左，但匹配发生失败时，模式T右移的计算方法却发生了较大的变化。
五、实验结果与结论：
（给出测试数据以及程序运行结果，并进行比较，得出自己的结论）
设计思想：
设文本串T，模式串为P。
首先将T与P进行左对齐，然后进行从右向左比较，若是某趟比较不匹配时，BM算法就采用两条启发式规则，即坏字符规则和好后缀规则，来计算模式串向右移动的距离，直到整个匹配过程的结束。
BE算法：
#include
#include
#include
main（）
{
chars[100];
chart[100];
inti,a,b,m,n;
printf（"*****pleaseinputastring:
"）;
scanf（"%s",s）;
printf（"pleaseinputsearchstring:
"）;
scanf（"%s",t）;
m=strlen（s）;
n=strlen（t）;
printf（"*******BF********\n"）;
for（i=0;i{
b=0;
a=i;
while（s[a]==t[b]&&b!
=n）
{
a++;
b++;
}
if（b==n）
{
printf（"success!
\n"）;
return0;
}
}
printf（"nofound!
:
%s\n\n",&t）;
return0;
}
KMP算法：
#include
#include
#include
main（）
{
chars[100];
chart[100];
inti,a,b,m,n;
printf（"*****pleaseinputastring:
"）;
scanf（"%s",s）;
printf（"pleaseinputsearchstring:
"）;
scanf（"%s",t）;
m=strlen（s）;
n=strlen（t）;
printf（"*******KMP********\n"）;
for（a=0;a<=m-n;a++）
{
b=0;
while（s[a]==t[b]&&b!
=n）
{
a++;
b++;
}
if（b==n）
{
printf（"success!
\n"）;
return0;
}
else
{
b=b+1;
a=a-b;
}
if（b=-1）
{b++;}
elsereturn0;
}
printf（"nofound!
:
%s\n\n",&t）;
return0;
}
BM算法：
#include
usingnamespacestd;
#include
#include
staticinttime=0;
//dist函数
intdist（charch,char*T）
{
intk=-1,t1;
t1=strlen（T）;
for（inti=0;i{
if（ch==T[i]&&ik=i+1;
if（ch==T[i]&&i==t1-1）
k=0;
}
if（k==-1）
k=0;
return
t1-k;
}
voidBM（char*S,char*T）
{
ints1,t1;
s1=strlen（S）;
t1=strlen（T）;
intj,i=t1-1;
while（i{
j=t1-1;
while（j>=0&&S[i]==T[j]）
{
i--;
j--;
}
if（j==-1）
{
cout<<"该串从第&i位开始匹配：
"<break;
}
else
{
time++;
i=i+dist（S[i],T）;
}
}
if（i>=s1）
cout<<"匹配不成功"<}
voidmain（）
{
int*next=newint;//给next指针分配空间
char*S=newchar;//给S指针分配空间
char*T=newchar;//给T指针分配空间
cout<<"请输入串S:
";
cin>>S;
cout<<"请输入串T:
";
cin>>T;
cout<<"BM算法:
";
BM（S,T）;
cout<<"一共执行循环"<}
实验心得：
蛮力法的算法设计，BF算法的思想最简单，但是比较刻板。
升级版的KMP和BM算法设计起来有一点难度，但是它们的思想要巧妙一点。
（此文档部分内容来源于网络，如有侵权请告知删除，文档可自行编辑修改内容，供参考，感谢您的配合和支持）
升级会员 