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

实用标准文档文案大全实验报告一串匹配问题班级：_计算机师_学号：2姓名：_一、实验题目：给定一个文本,在该文本中查找并定位任意给定字符串。二、实验目的：(1)深刻理解并掌握蛮力法的设计思想;(2)提高应用蛮力法设计算法的技能;(3)理解这样一个观点:用蛮力法设计的算法,一般来说,经过适度的努力后,都可以对算法的第一个版本进行一定程度的改良,改进其时间性能。三、实验要求：(1)实现BF算法;(2)实现BF算法的改进算法:KMP算法和BM算法;(3)对上述3个算法进行时间复杂性分析,并设计实验程序验证分析结果。四、算法描述（对算法主要部分进行伪代码描述或画出流程图）BF算法：基本思想：从主串S的第一个字符开始和模式T的第一个字符进行比较，若相等，则继续比较两者的后续字符；若不相等，则从主串S的第二个字符开始和模式T的第一个字符进行比较，重复上述过程，若T中的字符全部比较完毕，则说明本趟匹配成功；若最后一轮匹配的起始位置是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，准备下一趟比较；2.4如果T中所有字符均比较完毕，则返回匹配的起始下标；否则返回0；BM算法：基本思想：BM算法与KMP算法的主要区别是匹配操作的方向不同。虽然BM算法仅把匹配操作的字符比突顺序改为从右向左，但匹配发生失败时，模式T右移的计算方法却发生了较大的变化。实用标准文档文案大全开始主串S长度→m模式T长度→n0→iim0→bi→aS[a]=T[b]且b≠na加1b加1b=nYNYYYNNNBF算法结束开始主串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实用标准文档文案大全开始i≦主串S长度-1模式T长度-1→jj≧0且S[i]=T[j]i减1j减1j0YYYNNNBM算法结束0→a0→b0→z模式T长度-1→ii+DIST(T,S[i])→i实用标准文档文案大全五、实验结果与结论：（给出测试数据以及程序运行结果，并进行比较，得出自己的结论）设计思想：设文本串T，模式串为P。首先将T与P进行左对齐，然后进行从右向左比较，若是某趟比较不匹配时，BM算法就采用两条启发式规则，即坏字符规则和好后缀规则，来计算模式串向右移动的距离，直到整个匹配过程的结束。BE算法：#includestdio.h#includestring.h#includeconio.hmain(){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;im;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算法：#includestdio.h#includestring.h#includeconio.hmain(){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算法：#includeiostreamusingnamespacestd;#includestdio.h#includestring.hstaticinttime=0;//dist函数intdist(charch,char*T){intk=-1,t1;实用标准文档文案大全t1=strlen(T);for(inti=0;it1-1;i++){if(ch==T[i]&&it1)k=i+1;if(ch==T[i]&&i==t1-1)k=0;}if(k==-1)k=0;returnt1-k;}voidBM(char*S,char*T){ints1,t1;s1=strlen(S);t1=strlen(T);intj,i=t1-1;while(is1){j=t1-1;while(j=0&&S[i]==T[j]){i--;j--;实用标准文档文案大全}if(j==-1){cout该串从第&i位开始匹配：i+2endl;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:;cinS;cout请输入串T:;cinT;coutBM算法:;BM(S,T);cout一共执行循环time次endl;}实用标准文档文案大全实验心得：蛮力法的算法设计，BF算法的思想最简单，但是比较刻板。升级版的KMP和BM算法设计起来有一点难度，但是它们的思想要巧妙一点。