串匹配BM算法KMP算法BF算法.docx

实 验 报 告 一 串 匹 配 问 题 ?
班级： _计算机师 _学号： 2 姓名： _
一、实验题目 ：给定一个文本 , 在该文本中查找并定位任意给定字符串。
二、实验目的：
深刻理解并掌握蛮力法的式 T长
0→a
0→i
0→b
N
N
a≦
i<m
Y
Y
N
0→b
S[a]=T
[b]
且 b
i →a
Y
N
a 加 1
S[a]=T
b 加 1
[b] 且 b
Y
Y
a 加 1
N
b=n
b 加 1
next[b]
Y
a-b → a
b=n
Y
N
结
b=-1
N
结
b 加 1
BF算法
KMP算法
??
开
0→ a
0→ b
0→ z
模式 T长
N
i ≦主串 S
Y
模式 T长
j ≧
N
0
且
Y
减 1
减 1
Y N
j<0
i+DIST(T
结
BM算法
五、实验结果与结论： （给出测试数据以及程序运行结果，并进行比较，得出自己的结
论）
?设计思想：设文本串 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<m;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<