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

《串匹配BM算法、KMP算法、BF算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、：根本思想：从主串S的第一个字符开场和模式T的第一个字符进展比拟，假设相等，那么继续比拟两者的后续字符；假设不相等，那么从主串S的第二个字符开场和模式T的第一个字符进展比拟，重复上述过程，假设T中的字符全部比拟完毕，那么说明本趟匹配成功；假设最后一轮匹配的起始位置是n-m，那么主串S中剩下的字符缺乏够匹配整个模式T，匹配失败。这个算法称为朴素的模式匹配算法，简称BF算法。KMP算法：根本思想：1.在串S和串T中分别设比拟的起始下标i和j；2.循环直到S中所剩字符长度小于T的长度或T中所有字符均比拟完毕-.word.zl---2.1如果S[i]=T[j]，那

3、么继续比拟S和T的下一个字符；否那么2.2将j向右滑动到next[j]位置，即j=next[j]；2.3如果j=0，那么将i和j分别加1，准备下一趟比拟；2.4如果T中所有字符均比拟完毕，那么返回匹配的起始下标；否那么返回0；BM算法：根本思想：BM算法与KMP算法的主要区别是匹配操作的方向不同。虽然BM算法仅把匹配操作的字符比突顺序改为从右向左，但匹配发生失败时，模式T右移的计算方法却发生了较大的变化。-.word.zl---  开场主串S长度→m模式T长度→n0→ii

4、毕开场主串S长度→m模式T长度→n0→a0→ba≦M-NM-Nm-nS[a]=T[b]且b≠na加1b加1b=nYYYNNNKMP算法完毕next[b]→ba-b→ab=-1b加1 -.word.zl---开场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 -.word.zl---  五、实验结果与结论：〔给出测试数据以及程序运行结果，并进展比拟，得出自己的结论〕 设计思想：设文本串T，模式串为P。首先将T与P进展左对齐，然后进展从

5、右向左比拟，假设是某趟比拟不匹配时，BM算法就采用两条启发式规那么，即坏字符规那么和好后缀规那么，来计算模式串向右移动的距离，直到整个匹配过程的完毕。  BE算法：#include#include#includemain(){chars[100];chart[100];inti,a,b,m,n;printf("*****pleaseinputastring:");scanf("%s",s);printf("pleaseinputsearchstring:");scanf("%s",t);m=strle

6、n(s);n=strlen(t);printf("*******BF********");for(i=0;i#include#include-.word.zl---main(){chars[10

7、0];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********");for(a=0;a<=m-n;a++){b=0;while(s[a]==t[b]&&b!=n){a++;b++;}if(b==n){printf("success!");-.word.zl---re

8、turn0;}else{b=b+1;a=a-b;}if(b=-1)