欢迎来到天天文库
浏览记录
ID:55592604
大小:62.00 KB
页数:6页
时间:2020-05-19
《实验项目一 串匹配问题.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(i3、&&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(j4、5、(t[j]==t[k])){j++;k++;next[j]=k;break;}elsek=nex6、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){retu8、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.试验心得、
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(j4、5、(t[j]==t[k])){j++;k++;next[j]=k;break;}elsek=nex6、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){retu8、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.试验心得、
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.试验心得、
此文档下载收益归作者所有