串匹配问题：BF算法、KMP算法、BM算法

昆明理工大学信息工程与自动化学院学生实验报告（2010一2011学年第一学期）课程名称： 算法分析与设计 开课实验室：计算中心3102010年11月12日年级【、专业、班计科081班学号200810405339姓名赵丽成绩实验项目名称串匹配问题指导教师吴霖教师评语教师签名：年 月日一、 实验内容和目的1、 深刻理解并掌握蛮力算法的设计思想；2、 提高应用蛮力算法设计算法的技能；3、 理解这样一个观点:用蛮力法设计的算法，一般来说，经过适度的努力后，都可以对算法的第一个版本进行一定程度的改良，改进其时间性能。二、 实验原理及基本技术路线图（方框原理图）串匹配问题 给定两个串S二“ss„・s”和T二“tt„t”，在主12n 12m串S中查找子串T的过程称为串匹配，也称模式匹配。串匹配问题属于易解问题。串匹配问题的特征：（1） 算法的一次执行时间不容忽视：问题规模n很大，常常需要在大量信息中进行匹配；（2） 算法改进所取得的积累效益不容忽视：串匹配操作经常被调用,执行频率高。BF算法：基本思想：从主串S的第一个字符开始和模式T的第一个字符进行比较，若相等，则继续比较两者的后续字符；若不相等，则从主串S的第二个字符开始和模式T的第一个字符进行比较，重复上述过程,若T中的字符全部比较完毕，则说明本趟匹配成功；若最后一轮匹配的起始位置是n-m，则主串S中剩下的字符不足够匹配整个模式T，匹配失败。这个算法称为朴素的模式匹配算法，简称BF算法。KMP算法：在串S和串T中分别设比较的起始下标i和j；2•循环直到S中所剩字符长度小于T的长度或T中所有字符均比较完毕2.1如果S[i]=T[j],贝U继续比较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右移的计算方法却发生了较大的变化。设计思想：设文本串T,模式串为P。首先将T与P进行左对齐，然后进行从右向左比较，若是某趟比较不匹配时，BM算法就采用两条启发式规则，即坏字符规则和好后缀规则，来计算模式串向右移动的距离，直到整个匹配过程的结束。BF算法b加1KMP算法BM算法三、 所用仪器、材料（设备名称、型号、规格等）Windows7,MicrosoftVisualC++6.0四、 实验方法、步骤1、 实现BF算法；2、 实现BF算法的改进算法:KMP算法和BM算法;3、 观察并记录运行结果。五、 实验过程原始记录（数据、图表、计算等）源程序：#include"stdio.h"#include"conio.h"#includeviostream>//BF算法intBF(chars[],chart[]){inti;inta;intb;intm,n;m=strlen(s);//主串长度n=strlen(t);〃子串长度printf("\n*****BF*****算法\n");for(i=0;ivm;i++){b=0;a=i;while(s[a]=t[b]&&b!=n){a++;b++;}if(b==n){printf("查找成功!!\n\n");return0;}}printf("找不到%s\n\n",t);return0;}〃前缀函数值，用于KMP算法intGETNEXT(chart[],intb){intNEXT[10];NEXT[O]=-1;intj,k;j=0;k=-1;while(jvstrlen(t)){f((k==-l)ll(t[j]=t[k])){j++；k++;NEXT[j]=k;}elsek=NEXT[k];}b=NEXT[b];returnb;}〃KMP算法intKMP(chars[],chart[]){inta=0;intb=0;intm,n;m=strlen(s);//主串长度n=strlen(t);〃子串长度printf("\n*****KMP算法*****\n");while(av=m-n){while(s[a]=t[b]&&b!=n){a++;b++;}if(b==n){printf("查找成功!!\n\n");return0;}b=GETNEXT(t,b);a=a-b;if(b=-l)b++;printf("找不到％s\n\n",t);return0;}〃滑动距离函数，用于BM算法intDIST(chart[],charc){inti=0,x=1;intn;n=strlen(t);while(x&&i!=n-1){if(t[i]==c)x=0;elsei++;}if(i!=n-1)n=n-1-i;returnn;}//BM算法intBM(chars[],chart[]){inta=0;intb=0;inti,j;printf("\n*****BM算法*****\n");intz=0;i=strlen(t)-1;while(iv=strlen(s)-1){j=strlen(t)-1;while(j>=0&&s[i]==t[j]){j--；i--;if(jvO){printf("查找成功!!\n\n");return0;}elsei=i+DIST(t,s[i]);}printf("找不到%s\n\n",t);return0;}voidmain(){chars[]={'\0'}; 〃主串Sintn=10;chart[]={'\0'}; 〃模式Tprintf("\n 串匹配问题 \n");printf("\n输入主串S\nS=");scanf("%s",&s);printf("\n输入子串T\nT=");scanf("%s",&t);printf("主串长%d，子串长为％d\n",strlen(s),strlen(t));BF(s,t);〃BF算法KMP(s,t); 〃KMP算法BM(s,t);//BM算法'C:\Users\li\Desktop\算法分折与设计\目15对\DEbug\串配对总灼串匹配问题输入主串£S=ababcabcacbab输入子串TT=abca