计算机算法实验报告BF和KMP.doc

天津市大学软件学院实验报告课程名称：串匹配算法实验姓名： 陈小龙 学号：1150210403班级： 业务1114 串匹配问题一、实验题目：给定一个主串，在该主串中查找并定位任意给定字符串。二、实验目的：(1)深刻理解并掌握蛮力法的设计思想；(2)提高应用蛮力法设计算法的技能；(3)理解这样一个观点：用蛮力法设计的算法，一般来说，经过适度的努力后，都可以对算法的第一个版本进行一定程度的改良，改进其时间性能。三、实验分析：串匹配问题的BF算法1 在串S中和串T中设比较的下标i=1和j=1; 2 循环直到S中所剩字符个数小于T的长度或T中所有字符均比较完 2.1 k=i 2.2 如果Si=Tj,则比较S和T的下一字符,否则 2.2 将i和j回溯(i=k+1; j=1)3 如果T中所有字符均比较完,则匹配成功,返回k 否则匹配失败,返回0 时间复杂度：设匹配成功发生在si处，则在i-1趟不成功的匹配中比较了（i-1）m次，第i趟成功匹配共比较了m次，所以总共比较了im次，因此平均比较次数是：i=1n-m+1pi(im)= i=1n-m+11n-m+1(im)= m(n-m+2)2一般情况下，mn,因此最坏情况下时间复杂度是(nm)。串匹配问题的KMP算法实现过程：在串S和串T中高比较的起始下标i和j；循环直到S中所剩字符小于T的长度或T的所有字符均比较完（如果Si=Tj,则继续比较S和T的下一个字符；否则将j向右滑动到nextj位置，即j=nextj;如果j=0,则将i和j分别+1，准备下趟比较，至于其中的next在此不作详细讲解）；如果T中所有字符均比较完，则匹配成功，返回匹配的起始下标；否则匹配失败，返回0。时间复杂度：(n+m)，当mn时，KMP算法的时间复杂性是(n)。四、实验所用语言和运行环境C+，运行环境Microsoft Visual C+ 6.0五、实验过程的原始记录BF算法程序代码#include#includevoid main() cout请输入主串并且以0和回车结束endl;char s100;char t100;for(int m=0;msm;if(sm=0)sm=0;break;cout您输入的主串为：;for(int o=0;ostrlen(s);+o)coutso;coutendl;cout主串长度：;coutstrlen(s); coutendlendl;cout请输入子串并且以0和回车结束endl;for(int n=0;ntn;if(tn=0)tn=0;break;cout您输入的子串为：;for(int a=0;astrlen(t);+a)coutta; coutendl; cout子串长度：; coutstrlen(t);coutendl;coutendl+BF算法+endl; int i,j,k,y=0; for(i=0;istrlen(s)-strlen(t)+1;) k=i; for(j=0;jstrlen(t);) if(si=tj) if(j=strlen(t)-1) cout找到了相同的字串：;cout位置在主串的第i-j+1的位置上; coutendl;y=1;break; +i; +j; else j=0;break;i=k+1;if(y=1)break;if(i=strlen(s)-strlen(t)+1&j!=strlen(t)-1)cout没有找到可以匹配的子串endl;程序执行结果：查找到了子串 没有查找到子串KMP算法程序代码#include#include/前缀函数值,用于KMP算法int GETNEXT(char t,int b)int NEXT10;NEXT0=-1;int j,k;j=0;k=-1;while(jstrlen(t)if (k=-1)|(tj=tk)j+;k+;NEXTj=k;else k=NEXTk;b=NEXTb;return b;int KMP(char s,char t)int a=0;int b=0;int m,n;m=strlen(s);/主串长度n=strlen(t);/子串长度coutendl+KMP算法+endl;while(a=m-n)while(sa=tb&b!=n)a+;b+;if(b=n)cout找到了相应的子串位置在主串：a-b+1endl;return 0;b=GETNEXT(t,b);a=a-b;if(b=-1) b+;cout没有找到匹配的子串！endl;return 0;void main() cout请输入主串并且以0和回车结束endl;char s100;char t100;for(int m=0;msm;if(sm=0)sm=0;break;cout您输入的主串为：;for(int o=0;ostrlen(s);+o)coutso;coutendl;cout主串长度：;coutstrlen(s); coutendlendl;cout请输入子串并且以0和回车结束endl;for(int n=0;ntn;if(tn=0)tn=0;break;cout您输入的