文档介绍：SANY标准化小组 #QS8QHH-HHGX8Q8-GNHHJ8-HHMHGN#
串匹配BM算法KMP算法BF算法
实验报告一串匹配问题
班级：_计算机师_学号：2姓名：_
一、实验题目：给定一个文本,在该主串S长度→m
模式T长度→n
0→a
0→b
a≦M-NM-Nm-n
S[a]=T[b]且b≠n
a加1
b加1
b=n
Y
Y
Y
N
N
N
KMP算法
结束
next[b]→b
a-b→a
b=-1
b加1
开始
i≦主串S长度-1
模式T长度-1→j
j≧0且S[i]=T[j]
i减1
j减1
j<0
Y
Y
Y
N
N
N
BM算法
结束
0→a
0→b
0→z
模式T长度-1→i
i+DIST(T,S[i])→i
五、实验结果与结论：（给出测试数据以及程序运行结果，并进行比较，得出自己的结论）
设计思想：设文本串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<>
#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++