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

1、天津市大学软件学院实验报告课程名称：串匹配算法实验姓名： 陈小龙学号：1150210403班级：业务1114串匹配问题一、实验题目：给定一个主串，在该主串中查找并定位任意给定字符串。二、实验目的：(1) 深刻理解并掌握蛮力法的设计思想；(2) 提高应用蛮力法设计算法的技能；(3) 理解这样一个观点：用蛮力法设计的算法，一般来说，经过适度的努力后， 都可以对算法的第一个版本进行一定程度的改良，改进其吋间性能。三、实验分析：串匹配问题的bf算法1在串s中和串t中设比较的下标i=l和j=l;2循环直到s中所剩字符个数小于t的长度或t中所有字符均比较完2.1 k=i2.2如果si=tj,则比较s和t的

2、下一字符，否则2.2 将 i 和 j 回溯(i=k+l;j=l)3如果t中所有字符均比较完，则匹配成功，返回k否则匹配失败，返回0时间复杂度：设匹配成功发生在si处，则在il趟不成功的匹配中比较了(il) xm次，第i趟成功匹配共比较了 m次，所以总共比较了 ixm次，因此平均比较 次数是：时2 pik(ixm)二工肚严】 孟三x(ikm)二沁严一般情况s, m«n,因此最坏情况卜时间复杂度是o (nxm)o串匹配问题的kmp算法实现过程：在串s和串t屮高比较的起始下标i和j；循环直到s屮所剩字符小 于t的长度或t的所有字符均比较完(如果si二tj,则继续比较s和t的下一 个字符;否

3、则将j向右滑动到nextfj位置,即j=nextj;如果j=0,则将i和j分别 + 1,准备下趟比较，至于其中的next在此不作详细讲解)；如果t中所有字符均 比较完，则匹配成功，返冋匹配的起始下标；否则匹配失败，返冋0。时间复杂度：0(n+m),当mvvn时，kmp算法的时间复杂性是0 )。四、实验所用语言和运行环境c+,运行环境 microsoft visual c+ 6. 0五、实验过程的原始记录bf算法程序代码#include<iostrcam h>#include<stringvoid main()cout«，z请输入主串并且以0和回车结束/z«

4、endl;char s100;char t 100;for (i nt in=0;m<100;m+)cin>>sm;if (sm =，0,)s m - 0'break;cout«/z您输入的主串为：；for(int o=0;o<strlen(s);+o)cout«so;cout«endl;cout<<"主串长度："；cout<<strlen (s);cout<<endl<<endl;cout«/z请输入子串并且以0和冋车结束，z«endl;for

5、 (int n=0;n<100;n+)cin»t n;if(tn= o')tn= 0'break;cout«z，您输入的子串为：；for(int a=0;a<strlen(t);+a)cout«t a;cout<<endl;cout«/z子串长度：； cout«strlen； cout<<endl;cout<<endl<<，/+bf 算法+"«endl;int i, j, k, y=0;for (i=0; kstrlen (s) -strlen (t

6、) +1;)k=i;for(j=0;j<strlen (t);)if (si=t j)if (j=strl en( t)-l)cout«zz找到了相同的字串：；cout«，z位置在主串的第i-j + l«的位置上; cout<<endl;y=l;break;+i；卄j;elsej=o； break;i二k+1;if(y=l)break;if (i=strlen (s) -strlen (t) +1&& j! =str len (t) -1) cout«，z没有找到可以匹配的子串z，«endl;程序执行结果：没有

7、查找到子串查找到了子串p:c- * sh iya ndebugbf.exeg ' d:c*+shiyandebugbf.exe"幘输入主串并且以0和回车结束wlkjfaeioraaewirs您趣入的主串为：wlkjfaeiowaewif 王串长度：16幘输入子串并且以0和回车结束ioraa0您魏入的子串为：iof" 存當长產：5请输入子串并且以0和回车结束 seinue0您筮入敢子串为：seinue子串长度：6+bf.+没有找到可以匣配的子串press any key to continue+bfiw+找到了相同萌孝串：位置在主串的第8的位置上 press any

8、key to continue.kmp算法程序代码# include<iostream.h># include<string>前缀函数值，用于kmp算法int getnext(char b)int next10;nextloj=-1;intj,k;j=0;k=-l;while(j<strlen(t)if(k=-l)|(tj=tk)j+；k+;nextj=k;1else k=nextk;b=nextb;return b;1int kmp(char s,char tj)int a=0;int b=0;int m,n;m=strlen(s); 主串长度 n=strlen

9、；子串长度 cout«endl«',+kmp 算法+"vvcndl; while(a<=m-n)while(sa=tb&&b!=n)a+; b+;if(b=n)h«a-b+l«endl;cout«h找到了相应的子串位置在主串： return 0;b=getnext(t,b);a=a-b;if(b=-l) b+;cout«n没有找到匹配的子串！ m«endl;return 0;1void main()cout«h请输入主串并且以0和回车结束m«endl;char s1

10、00;char t100;for(int m=0;m<100;m+)cin»sm;smj='0,;break;1cout«h您输入的主串为：”；for(int o=0;o<strlen(s);+o)cout«sfol;cout«endl;cout«h主串长度:”;cout«strlen(s);cout«endl«endl;cout«n请输入子串并且以0和冋车结束m«endl;for(int n=0;n<100;n+)cin»tn;if(tnl=,o,)tn=,

11、o,; break;cout«h您输入的子串为：for(int a=o;a<strlen(t);+a)cout«tal;cout«endl; cout«n子串长度：”; cout«strlen(t);cout«endl; kmp(s,t);1没有查到子串程序执行结果： 查找到子串w d:c + * shiyandebu gkmp.exer d:c * shiyandebugkm p .exe"请输入主串井且以b和回车结束；j iwerngasjdhf u0|塑塑入的主串为：；jw"ngasjdhfu 串长度$ isi请输入子串并且以0和回车结束 jdhfu0|您軸入的子串为* gasjdhfu学車长度：8+kmp_+ 找到了相应的子串位置在主