(实验报告1)串匹配BM算法和BF算法

电子科技大学成都学院 计算机 系

标 准 实 验 报 告

（实验）课程名称 《语言与算法分析》

电子科技大学成都学院计算机系制表

电 子 科 技 大 学成都学院

实 验 报 告

学生姓名：易兴 学 号：2940610408 指导教师：杨菊英 实验地点：实验室501 实验时间：2010年12月5日

一、实验室名称：《语言与算法分析》 二、实验项目名称：在字符串T中查找与S相对应的子字符串 三、实验学时：1

四、实验原理：又称BF算法，其主要思想：从S第一个字符开始与T第一个字符比较 。若相等，则逐个比较后续字符；不相等，从S第二个字符开始重新与T第一个字符进行比较。依次类推，若匹配成功，

则返回T第一个字符在S中的位置，否则匹配失败。 五、实验目的： 理解并掌握穷举法的设计思想；

六、实验内容：

#include using namespace std; #include #include static int time1=0,time2=0; //BF算法

void BF(char *S,char *T) {

int i=0,j=0,s1,t1;

s1=strlen(S); t1=strlen(T); while(iif(S[i]==T[j]) } if(j==t1) { } else } //dist函数

int dist(char ch,char *T) {

int k=-1,t1; t1=strlen(T); for(int i=0;iif(ch==T[i]&&i//BM算法

void BM(char *S,char *T) {

k=0; t1-k; return

k=i+1;

if(ch==T[i]&&i==t1-1) cout<<\"匹配不成功\"<cout<<\"匹配的起始下标为：\"<<(i-j+1)<i++; j++; time1++; } { i=i-j+1; j=0; time1++; }

else

k=0;

int s1,t1; s1=strlen(S); t1=strlen(T); int j,i=t1-1; while(iwhile(j>=0&&S[i]==T[j]) { i--; }

if(j==-1) } 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<<\"BF算法: \"; BF(S,T);

cout<<\"一共执行循环\"<cout<<\"一共执行循环\"<{ } { }

time2++; i=i+dist(S[i],T);

cout<<\"匹配的起始下标为：\"<else

七、实验器材（设备、元器件）： VC++，计算机

八、实验步骤：1，先理解题意，大概构思。

2，在建立函数关系实现BF和BM算法。 3，建立主函数调用算法函数。 4，运行程序，计算结果。

九、实验数据及结果分析：

十、实验结论：

十一、总结及心得体会：

十二、对本实验过程及方法、手段的改进建议：

报告评分：

指导教师签字