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

1、实验报告一 串匹配问题  班级：_计算机师 _ 学 号： 2 姓 名：_一、实验题目：给定一个文本, 在该文本中查找并定位任意给定字符串。 2、 实验目的：(1) 深刻理解并掌握蛮力法的设计思想; (2) 提高应用蛮力法设计算法的技能; (3) 理解这样一个观点: 用蛮力法设计的算法, 一般来说, 经过适度的努力后, 都可以对算法的第一个版本进行一定程度的改良, 改进其时间性能。 三、实验要求： (1) 实现 BF算法; (2) 实现 BF算法的改进算法: KMP 算法和 BM 算法; (3) 对上述3个算法进行时间复杂性分析, 并设计实验程序验证分析结果。 4、 算法描述（对算法主

2、要部分进行伪代码描述或画出流程图）BF算法：基本思想：从主串S的第一个字符开始和模式T的第一个字符进行比较，若相等，则继续比较两者的后续字符；若不相等，则从主串S的第二个字符开始和模式T的第一个字符进行比较，重复上述过程，若T中的字符全部比较完毕，则说明本趟匹配成功；若最后一轮匹配的起始位置是n-m，则主串S中剩下的字符不足够匹配整个模式T，匹配失败。这个算法称为朴素的模式匹配算法，简称BF算法。KMP算法：基本思想：1. 在串S和串T中分别设比较的起始下标i和j；2. 循环直到S中所剩字符长度小于T的长度或T中所有字符均比较完毕2.1 如果Si=Tj，则继续比较S和T的下一个字符；否则2.2

3、 将j向右滑动到nextj位置，即j=nextj；2.3 如果j=0，则将i和j分别加1，准备下一趟比较；2.4 如果T中所有字符均比较完毕，则返回匹配的起始下标；否则返回0；BM算法：基本思想：BM算法与KMP算法的主要区别是匹配操作的方向不同。虽然BM算法仅把匹配操作的字符比突顺序改为从右向左，但匹配发生失败时，模式T右移的计算方法却发生了较大的变化。  开始主串S长度m模式T长度n0ii<m0biaSa=Tb且bna加1b加1b=nYNYYYNNNBF算法结束开始主串S长度m模式T长度n0a0baM-NM-Nm-nSa=Tb且bna加1b加1b=nYYYNNNK

4、MP算法结束nextbba-bab=-1b加1 开始i主串S长度-1模式T长度-1jj0且Si=Tji减1j减1j<0YYYNNNBM算法结束0a0b0z模式T长度-1ii+DIST(T,Si)i   五、实验结果与结论：（给出测试数据以及程序运行结果，并进行比较，得出自己的结论） 设计思想：设文本串T，模式串为P。首先将T与P进行左对齐，然后进行从右向左比较，若是某趟比较不匹配时，BM算法就采用两条启发式规则，即坏字符规则和好后缀规则，来计算模式串向右移动的距离，直到整个匹配过程的结束。  BE算法：#include

5、 <stdio.h>#include <string.h>#include <conio.h>main()char s100;char t100;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

6、=0;i<m;i+)b=0;a=i;while(sa=tb&&b!=n)a+;b+;if(b=n)printf("success!n");return 0; printf("no found!:%snn",&t); return 0; KMP算法：#include <stdio.h>#include <string.h>#include <conio.h>main()char s100;char t100;int i,a,b,m,n;printf("*please in

7、put 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(sa=tb&&b!=n)a+;b+;if(b=n)printf("success!n");return 0;elseb=b+1;a=a-b;if(b=-1)b+;el

8、se return 0; printf("no found!:%snn",&t); return 0; BM算法：#include <iostream>using namespace std;#include <stdio.h>#include <string.h>static int time=0;/dist函数int dist(char ch,char *T) int k=-1,t1; t1=strlen(T); for(int i=0;i<t1-1;i+) if(ch=Ti&&i<t1)

9、k=i+1;if(ch=Ti&&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<s1) j=t1-1; while(j>=0&&Si=Tj) i-; j-; if(j=-1) cout<<"该串从第&i位开始匹配："<<i+2<<endl; break; else time+; i=i+d

10、ist(Si,T); if(i>=s1) cout<<"匹配不成功"<<endl;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<&