欢迎来到天天文库
浏览记录
ID:70008023
大小:221.00 KB
页数:11页
时间:2021-11-14
《串匹配BM算法、KMP算法、BF算法》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、------------------------------------------作者xxxx------------------------------------------日期xxxx串匹配BM算法、KMP算法、BF算法【精品文档】实验报告一串匹配问题 班级:_计算机师_学号:2姓名:_一、实验题目:给定一个文本,在该文本中查找并定位任意给定字符串。二、实验目的:(1)深刻理解并掌握蛮力法的设计思想;(2)提高应用蛮力法设计算法的技能;(3)理解这样一个观点:用蛮力法设计的算法,一般来说,经过适度的努力后
2、,都可以对算法的第一个版本进行一定程度的改良,改进其时间性能。三、实验要求:(1)实现BF算法;(2)实现BF算法的改进算法:KMP算法和BM算法;(3)对上述3个算法进行时间复杂性分析,并设计实验程序验证分析结果。四、算法描述(对算法主要部分进行伪代码描述或画出流程图)BF算法:基本思想:从主串S的第一个字符开始和模式T的第一个字符进行比较,若相等,则继续比较两者的后续字符;若不相等,则从主串S的第二个字符开始和模式T的第一个字符进行比较,重复上述过程,若T中的字符全部比较完毕,则说明本趟匹配成功;若最后一轮匹
3、配的起始位置是n-m,则主串S中剩下的字符不足够匹配整个模式T,匹配失败。这个算法称为朴素的模式匹配算法,简称BF算法。KMP算法:基本思想:1.在串S和串T中分别设比较的起始下标i和j;2.循环直到S中所剩字符长度小于T的长度或T中所有字符均比较完毕2.1如果S[i]=T[j],则继续比较S和T的下一个字符;否则2.2将j向右滑动到next[j]位置,即j=next[j];2.3如果j=0,则将i和j分别加1,准备下一趟比较;如果T中所有字符均比较完毕,则返回匹配的起始下标;否则返回0;BM算法:基本思想:BM
4、算法与KMP算法的主要区别是匹配操作的方向不同。虽然BM算法仅把匹配操作的字符比突顺序改为从右向左,但匹配发生失败时,模式T【精品文档】【精品文档】右移的计算方法却发生了较大的变化。 开始主串S长度→m模式T长度→n0→ii5、开始i≦主串S长度-1模式T长度-1→jj≧0且S[i]=T[j]i减1j减1j<0YYYNNNBM算法结束0→a0→b0→z模式T长度-1→ii+DIST(T,S[i])→i 【精品文档】【精品文档】五、实验结果与结论:(给出测试数据以及程序运行结果,并进行比较,得出自己的结论) 设计思想:设文本串T,模式串为P。首先将T与P进行左对齐,然后进行从右向左比较,若是某趟比较不匹配时,BM算法就采用两条启发式规则,即坏字符规则和好后缀规则,来计算模式串向右移动的距离,直到整个匹配过程的结束。 BE算法:#in6、clude#include#includemain(){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********");for(i=0;i7、{b=0;a=i;while(s[a]==t[b]&&b!=n){a++;b++;}【精品文档】【精品文档】if(b==n){printf("success!");return0;}}printf("nofound!:%s",&t);return0;} KMP算法:#include#include#includemain(){chars[100];【精品文档】【精品文档】chart[100];inti,a,b,m,n;printf("*****p8、leaseinputastring:");scanf("%s",s);printf("pleaseinputsearchstring:");scanf("%s",t);m=strlen(s);n=strlen(t);printf("*******KMP********");for(a=0;a<=m-n;a++){b=0;while(s[a]==t[b]&&b!=n){
5、开始i≦主串S长度-1模式T长度-1→jj≧0且S[i]=T[j]i减1j减1j<0YYYNNNBM算法结束0→a0→b0→z模式T长度-1→ii+DIST(T,S[i])→i 【精品文档】【精品文档】五、实验结果与结论:(给出测试数据以及程序运行结果,并进行比较,得出自己的结论) 设计思想:设文本串T,模式串为P。首先将T与P进行左对齐,然后进行从右向左比较,若是某趟比较不匹配时,BM算法就采用两条启发式规则,即坏字符规则和好后缀规则,来计算模式串向右移动的距离,直到整个匹配过程的结束。 BE算法:#in
6、clude#include#includemain(){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********");for(i=0;i7、{b=0;a=i;while(s[a]==t[b]&&b!=n){a++;b++;}【精品文档】【精品文档】if(b==n){printf("success!");return0;}}printf("nofound!:%s",&t);return0;} KMP算法:#include#include#includemain(){chars[100];【精品文档】【精品文档】chart[100];inti,a,b,m,n;printf("*****p8、leaseinputastring:");scanf("%s",s);printf("pleaseinputsearchstring:");scanf("%s",t);m=strlen(s);n=strlen(t);printf("*******KMP********");for(a=0;a<=m-n;a++){b=0;while(s[a]==t[b]&&b!=n){
7、{b=0;a=i;while(s[a]==t[b]&&b!=n){a++;b++;}【精品文档】【精品文档】if(b==n){printf("success!");return0;}}printf("nofound!:%s",&t);return0;} KMP算法:#include#include#includemain(){chars[100];【精品文档】【精品文档】chart[100];inti,a,b,m,n;printf("*****p
8、leaseinputastring:");scanf("%s",s);printf("pleaseinputsearchstring:");scanf("%s",t);m=strlen(s);n=strlen(t);printf("*******KMP********");for(a=0;a<=m-n;a++){b=0;while(s[a]==t[b]&&b!=n){
此文档下载收益归作者所有