实验项目一 串匹配问题.doc

《实验项目一 串匹配问题.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验项目一串匹配问题1.实验题目给定一个文本，在该文本中任意查找并定位任意给定字符串。2.实验目的（1）深刻理解并掌握蛮力法的设计思想；（2）提高应用蛮力法设计算法的技能；（3）理解这样一个观点：用蛮力法设计的算法，一般来说，经过适度的努力后，都可以对算法的第一个版本进行一定程度的改良，改进其时间性能。3.实验要求（1）实现BF算法；（2）实现BF算法的改进算法：KMP算法和BM算法；（3）对上述三个算法进行时间复杂性分析，并设计实验程序验证分析结果。4.实验提示BF算法，KMP算法和BM算法都是串匹配问题中的经典算法，BF算法和KMP算法请参见本章第3.2节。下面介绍BM算法。BM算法是B

2、oyer和Moore共同设计的快速匹配算法。BM算法与KMP算法的主要区别是匹配操作的方向不同。虽然BM算法仅把匹配操作的字符比较顺序改为从左到右，但匹配发生失败时，模式T右移的计算方法却发生了较大的变化。5.实验代码BF算法代码#include#include#defineN50voidmain(){chara[N],b[N];printf("请输入待匹配的两个字符串，主串a为:");gets(a);printf("模式串b为:");gets(b);inti=1,j=1,s,t;s=strlen(a);t=strlen(b);while(i

3、&&j=t)printf("从a串的%d个字符开始匹配",i-j+1);elseprintf("匹配失败");}KMP算法代码#include#include#defineN50voidGetNext(chart[],intnext[]){next[1]=0;intj=1,k=0,h;h=strlen(t);while(j

4、

5、(t[j]==t[k])){j++;k++;next[j]=k;break;}elsek=nex

6、t[k];}voidmain(){chars[N],t[N];intnext[N]={0};printf("请输入主串s:");gets(s);printf("请输入模式串t:");gets(t);inti=1,j=1,k=strlen(s)-1,h=strlen(t)-1;while((i<=k)&&(j<=h)){if(s[i]==t[j]){i++;j++;}else{GetNext(t,next);j=next[j];{if(j==0){i++;j++;}}}}if(j>h)printf("匹配的起始下表为:%d",i-j+1);elseprintf("匹配失败");

7、}BM算法代码#include#include#defineN50intGetDist(chart[],charc){inti,k=0;intm;m=strlen(t)-1;for(i=m;i>0;i--){if(t[i]==c){k=i;break;}}if((k!=m)&&(k!=0))returnm-k;elsereturnm;}intBM(chars[],chart[],intn,intm){inti,j;i=m;while(i<=n){j=m;while(j>0&&(s[i]==t[j])){j=j-1;i=i-1;}if(j==0){retu

8、rni+1;break;}else{i+=GetDist(t,s[i]);}}return0;}voidmain(){chars[N],t[N];intr,n,m;printf("请输入主串s:");gets(s);printf("请输入模式串t:");gets(t);n=strlen(s)-1;m=strlen(t)-1;r=BM(s,t,n,m);if(r!=0)printf("匹配的起始下标为:%d",r);elseprintf("匹配失败");}1.实验结果BF算法实验结果KMP算法实验结果BM算法实验结果时间复杂度分析算法时间复杂度BFO（n*m）KMPO（n）BMO（

9、n/3）1.试验心得、