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

1、昆明理工大学信息工程与自动化学院学生实验报告(2010(201020112011 学年第一学期)课程名称：算法分析与设计开课实验室：计算中心 3102010 年 11 月12 日年级、专业、班计科 081 班学号200810405339姓名赵丽成绩实验项目名称用匹配问题指导教师i=r.i=r.患教师评语教师签名：年月日实验内容和目的1、深刻理解并掌握蛮力算法的设计思想；2、提高应用蛮力算法设计算法的技能；3、理解这样一个观点：用蛮力法设计的算法，一般来说，经过适度的努力后，都可以对算法的第一个版本进行一定程度的改良，改进其时间性能。实验原理及基本技术路线图(方框原理图)匹配问题给定两个用 S=

2、S1S2,Sn”和 T=t1t2,tm”，在主用 S 中查找子用 T 的过程称为用匹配，也称模式匹配。用匹配问题属于易解问题。用匹配问题的特征：(1)算法的一次执行时间不容忽视：问题规模 n 很大，常常需要在大量信息中进行匹配；(2)算法改进所取得的积累效益不容忽视：用匹配操作经常被调用，执行频率高。BF 算法：基本思想：从主用 S 的第一个字符开始和模式 T 的第一个字符进行比较，若相等，则继续比较两者的后续字符；若不相等，则从主用 S 的第二个字符开始和模式 T 的第一个字符进行比较，重复上述过程，若 T 中的字符全部比较完毕，则说明本趟匹配成功；若最后一轮匹配的起始位置是n-m,则主用S

3、中剩下的字符不足够匹配整个模式T,匹配失败。这个算法称为朴素的模式匹配算法，简称 BF 算法。KMF#法：1 .在用 S 和用 T 中分别设比较的起始下标 i 和 j;2 .循环直到 S 中所剩字符长度小于 T 的长度或 T 中所有字符均比较完毕2.1如果 Si=Tj,则继续比较 S 和 T 的下一个字符；否则2.2将 j 向右滑动到 nextj位置，即 j=nextj;2.3如果 j=0,则将 i 和 j 分别加 1,准备下一趟比较；2.4如果 T 中所有字符均比较完毕，则返回匹配的起始下标；否则返回 0;BM 算法：BM 算法与 KMF法的主要区别是匹配操作的方向不同。虽然 BM 算法仅把

4、匹配操作的字符比突顺序改为从右向左，但匹配发生失败时，模式 T 右移的计算方法却发生了较大的变化。设计思想：设文本用 T,模式用为 P。首先将 T 与 P 进行左对齐，然后进行从右向左比较，若是某趟比较不匹配时，BM 算法就采用两条启发式规则，即坏字符规则和好后缀规则，来计算模式用向右移动的距离，直到整个匹配过程的结束。BF 算法KMP 算法四、1、2、3、BM 算法i+DIST(T,Si)-i1所用仪器、材料（设备名称、型号、规格等）Windows7,MicrosoftVisualC+6.0实验方法、步骤实现 BF 算法;实现 BF算法的改进算法：KMP算法和BM算法;观察并记录运行结果。实

5、验过程原始记录（数据、图表、计算等）源程序：#includestdio.h#includeconio.h#include/BF 算法intBF(chars,chart)(inti;inta;intb;intm,n;m=strlen(s);主用长度n=strlen(t);/子用长度 printf(n*BF*算法n);for(i=0;im;i+)(b=0;a=i;while(sa=tb&b!=n)(a+;b+;if(b=n)(printf(查找成功！!nn);return0;printf(找不到snn,t);return0;/前缀函数值，用于 KMP 算法intGETNEXT(chart

6、口,intb)(intNEXT10;NEXT0=-1;intj,k;j=0;k=-1;while(jstrlen(t)(if(k=-i)|(tj=tk)(j+;k+;NEXTj=k;elsek=NEXTk;b=NEXTb;returnb;/KMP 算法intKMP(chars,chart)(inta=0;intb=0;intm,n;m=strlen(s);主用长度n=strlen(t);/子用长度 printf(n*KMP 算法*n);while(a=m-n)(while(sa=tb&b!=n)(a+;b+;if(b=n)(printf(查找成功！!nn);return0;b=GETN

7、EXT(t,b);a=a-b;if(b=-1)b+;printf(找不到%snn,t);return0;)/滑动距离函数，用于 BM 算法intDIST(chart 口,charc)inti=0,x=1;intn;n=strlen(t);while(x&i!=n-1)if(ti=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(i=0&si=tj)j-;i-;if(j0)(printf(查找成功!nn);return0;)elsei=i+DIST(t,si);)printf(找不到snn,t);return0;)voidmain()(chars=0;主用 Sintn=10;chart=0;/模式 Tprintf(n 申匹配问题n);printf(n 输入主用 SnS=);scanf(%s,&s);printf(n 输入子用TnT=);scanf(%s,&t);printf(主用长d,子用长为%dn,strlen(s),strlen(t);BF(s,t);/BF 算法KMP(s,t);