实验报告一串匹配问题
班级:_计算机师 _ 学号: 2 姓名:_
一、实验题目:给定一个文本, 在该文本中查找并定位任意给定字符串。
二、实验目的:
(1) 深刻理解并掌握蛮力法的设计思想;
(2) 提高应用蛮力法设计算法的技能;
(3) 理解这样一个观点: 用蛮力法设计的算法, 一般来说, 经过适度的努力后,
都可以对算法的第一个版本进行一定程度的改良, 改进其时间性能。
三、实验要求:
(1) 实现 BF算法;
(2) 实现 BF算法的改进算法: KMP 算法和 BM 算法;
(3) 对上述3个算法进行时间复杂性分析, 并设计实验程序验证分析结果。
四、算法描述(对算法主要部分进行伪代码描述或画出流程图)
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右移的计算方法却发生了较大的变化。
开主串S 长度
模式T 长度
0→i
i0→b
i →a
S[a]=T[b ]且b ?n a 加1
b 加1
b=n
Y
N
Y Y
Y
N
N
N
BF 算法
结
开
主串S 长度
→m
0→a 0→b
a ≦
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 长
模式T 长
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 长
i+DIST(T,S
五、实验结果与结论:(给出测试数据以及程序运行结果,并进行比较,得出自己的结论)
设计思想:设文本串T,模式串为P。首先将T与P进行左对齐,然后进行从右向左比较,若是某趟比较不匹配时,BM算法就采用两条启发式规则,即坏字符规则和好后缀规则,来计算模式串向右移动的距离,直到整个匹配过程的结束。
BE算法:
#include
#include
#include
main()
{
char s[100];
char t[100];
int i,a,b,m,n;
printf("*****please input a string:");
scanf("%s",s);
printf("please input search string:");
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");
return 0;
}
}
printf("no found!:%s\n\n",&t);
return 0;
}
KMP算法:
#include
#include
#include
main()
{
char s[100];
char t[100];
int i,a,b,m,n;
printf("*****please input a string:"); scanf("%s",s);
printf("please input search string:"); 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");
return 0;
}
else
{
b=b+1;
a=a-b;
}
if(b=-1)
{b++;}
else return 0;
}
printf("no found!:%s\n\n",&t); return 0;
}
BM算法:
#include
using namespace std;
#include
#include
static int time=0;
//dist函数
int dist(char ch,char *T) {
int k=-1,t1;
t1=strlen(T);
for(int i=0;iif(ch==T[i]&&ik=i+1;
if(ch==T[i]&&i==t1-1) k=0;
}
if(k==-1)
k=0;
return
t1-k;
}
void BM(char *S,char *T)
{
int s1,t1;
s1=strlen(S);
t1=strlen(T);
int j,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<<"匹配不成功"<}
void main()
{
int *next=new int;//给next指针分配空间
char *S=new char;//给S指针分配空间
char *T=new char;//给T指针分配空间
cout<<"请输入串S:";
cin>>S;
cout<<"请输入串T:";
cin>>T;
cout<<"BM算法: ";
BM(S,T);
cout<<"一共执行循环"<