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

实

验

报

告

一

串

匹

配

问

题?班级：计算师号：姓名：一、实题目：给定一个文本在该文本中查找并定位任意给定字符串。二、实目的：(1)深刻理解并掌握蛮力法的设计思想;(2)提高应用蛮力法设计算法的技能;(3)理解这样一个观点:用蛮力法设计的算法一般来说,经过适度的努力后,都可以对算法的第一个版本进行一定程度的改良改进其时间性能。三、实要求：(1)实现BF算法;(2)实现BF算法的改进算法:KMP算法和BM算法(3)对上述3个算法进行时间复杂性分析,并设计实验程序验证分析结果。四、算描述（对算法主要部分进行伪代码描述或画出流程图）BF法：基本思想：从主串S的第一个字符开始和模式T第一个字符进行比较，若相等，则继续比较两者的后续字符；若不相等，则从主串的第二个字符开始和模式T第一个字符进行比较，重复上述过程，若T的字符全部比较完毕，则说明本趟匹配成功；若最后一轮匹配的起始位置是n-，则主串S中剩下的字符不足够匹配整个模式T，匹配失败。这个算法称为朴素的模式匹配算法，简称算法。KMP法：基本思想：1.在串S和串T中分别设比较的起始下标ij；2.循环直到S中所剩字符长度小于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中所有字符均比较完毕，则返回匹配的起始下标；否则返回；BM法：基本思想：BM算法与KMP算法的主要区别是匹配操作的方向不同。虽然算法仅把匹配操作的字符比突顺序改为从右向左，但匹配发生失败时，模式T右移的计算方法却发生了较大的变化。

开主串S长模式T长→i

开主串S长→aNN

≦i<m

YY

N→ba

S[a]=T[YN

a1S[a]=T[b加1Ya加1b加1

Y

b=n

N→→aYb=n结

N

结

Y

b=-1

Nb1BF算法??

KMP算法

开→a→zN主串SY模式T长且Yi1j1

NY

Nj<0i+DIST(T,结BM算法五、实验结果与结论（给出测试数据以及程序运行结果，并进行比较，得出自己的结论）?设计思想：设文本串T，模式串P。首先将T与P进行左对齐，然后进行从右向左比较，若是某趟比较不匹配时BM算法就采用两条启发式规则，即坏字符规则和好后

缀规则，来计算模式串向右移动的距离，直到整个匹配过程的结束。BE法：#include<stdio.h>#include<string.h>#include<conio.h>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<stdio.h>#include<string.h>#include<conio.h>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++;}if(b==n)

{printf("success!\n");return0;}else{b=b+1;a=a-b;}if(b=-1){b++;}elsereturn0;}printf("nofound!:%s\n\n",&t);return0;}?

BM

算法：函数{

{}}voidBM(char*S,char*T){ints1,t1;s1=strlen(S);t1=strlen(T);intj,i=t1-1;while(i<s1){j=t1-1;while(j>=0&&S[i]==T[j]){i--;j--;}

if(j==-1){cout<<"该串从第&i位开始匹配："<<i+2<<endl;break;}else{time++;i=i+dist(S[i],T);}}if(i>=s1)cout<<"匹配不成功"<<endl;}voidmain(){int*next=newint;//给next指针分配空间char*S=newchar;//给S指针分配空间char*T=newchar;//给T指针分配空间cout<<"请输入串S:";cin>>S;cout<<"请输入串T:";cin>>T;co