串匹配问题BF算法KMP算法BM算法.docx
串匹配问题BF算法KMP算法BM算法一、 实验内容和目的 1、 深刻理解并掌握蛮力算法的设计思想； 2、 提高应用蛮力算法设计算法的技能； 3、 理解这样一个观点:用蛮力法设计的算法，一般来说，经过适度的努力后，都可以对算法的第一个版本进行一定程度的改良，改进其时间性能。 二、 实验原理及基本技术路线图 串匹配问题给定两个串S=“s1s2sn” 和T=“t1t2tm”，在主串S中查找子串T的过程称为串匹配，也称模式匹配。 串匹配问题属于易解问题。 串匹配问题的特征： 算法的一次执行时间不容忽视：问题规模 n 很大，常常需要在大量信息中进行匹配； 算法改进所取得的积累效益不容忽视：串匹配操作经常被调用，执行频率高。 BF算法： 基本思想：从主串S的第一个字符开始和模式T的第一个字符进行比较，若相等，则继续比较两者的后续字符；若不相等，则从主串S的第二个字符开始和模式T的第一个字符进行比较，重复上述过程，若T中的字符全部比较完毕，则说明本趟匹配成功；若最后一轮匹配的起始位置是n-m，则主串S中剩下的字符不足够匹配整个模式T，匹配失败。这个算法称为朴素的模式匹配算法，简称BF算法。 KMP算法： 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算法与KMP算法的主要区别是匹配操作的方向不同。虽然BM算法仅把匹配操作的字符比突顺序改为从右向左，但匹配发生失败时，模式T右移的计算方法却发生了较大的变化。 设计思想：设文本串T，模式串为P。首先将T与P进行左对齐，然后进行从右向左比较，若是某趟比较不匹配时，BM算法就采用两条启发式规则，即坏字符规则和好后缀规则，来计算模式串向右移动的距离，直到整个匹配过程的结束。 开始 主串S长度m 模式T长度n 0i N i<m Y 0b ia N Sa=Tb且bn Y a加1 b加1 Y b=n N 结束 BF算法 开始 主串S长度m 模式T长度n 0a 0b N am-n Y N Sa=Tb且bn Y a加1 b加1 Y b=n N nextbb a-ba Y b=-1 结束 N b加1 KMP算法 开始 Y Y N 0a 0b 0z 模式T长度-1i i主串S长度-1 Y 模式T长度-1j j0且Si=Tj N i减1 j减1 N j<0 i+DIST(T,Si)i 结束 BM算法 三、 所用仪器、材料 Windows 7，Microsoft Visual C+ 6.0 四、 实验方法、步骤 1、 实现BF算法； 2、 实现BF算法的改进算法:KMP算法和BM算法； 3、 观察并记录运行结果。 五、 实验过程原始记录(数据、图表、计算等) 源程序： #include "stdio.h" #include "conio.h" #include <iostream> /BF算法 int BF(char s,char t) int i; int a; int b; int m,n; m=strlen(s); /主串长度 n=strlen(t); /子串长度 printf("n*BF*算法n"); for(i=0;i<m;i+) b=0; a=i; while(sa=tb&&b!=n) a+; b+; if(b=n) printf("查找成功!nn"); return 0; printf("找不到%snn",t); return 0; /前缀函数值,用于KMP算法 int GETNEXT(char t,int b) int NEXT10; NEXT0=-1; int j,k; j=0; k=-1; while(j<strlen(t) if (k=-1)|(tj=tk) j+; k+; NEXTj=k; else k=NEXTk; b=NEXTb; return b; /KMP算法 int KMP(char s,char t) int a=0; int b=0; int m,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"); return 0; b=GETNEXT(t,b); a=a-b; if(b=-1) b+; printf("找不到%snn",t); return 0; /滑动距离函数,用于BM算法 int DIST(char t,char c) int i=0,x=1; int n; n=strlen(t); while(x&&i!=n-1) if(ti=c) x=0; else i+; if(i!=n-1) n=n-1-i; return n; /BM算法 int BM(char s,char t) int a=0; int b=0; int i,j; printf("n*BM算法*n"); int z=0; i=strlen(t)-1; while(i<=strlen(s)-1) j=strlen(t)-1; while(j>=0&&si=tj) j-; i-; if(j<0) printf("查找成功!nn"); return 0; else i=i+DIST(t,si); printf("找不到%snn",t); return 0; void main char s='0' /主串S int n=10; char t='0' /模式T printf("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); /KMP算法 BM(s,t); /BM算法
