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

天津市大学软件学院

实验报告

课程名称：串匹配算法实验

姓名： *** 学号：********** 班级： 业务1114

串匹配问题

一、实验题目：

给定一个主串，在该主串中查找并定位任意给定字符串。 二、实验目的：

(1)深刻理解并掌握蛮力法的设计思想； (2)提高应用蛮力法设计算法的技能；

(3)理解这样一个观点：用蛮力法设计的算法，一般来说，经过适度的努力后，都可以对算法的第一个版本进行一定程度的改良，改进其时间性能。 三、实验分析：

串匹配问题的BF算法

1 在串S中和串T中设比较的下标i=1和j=1;

2 循环直到S中所剩字符个数小于T的长度或T中所有字符均比较完 2.1 k=i

2.2 如果S[i]=T[j],则比较S和T的下一字符,否则 2.2 将i和j回溯(i=k+1; j=1)

3 如果T中所有字符均比较完,则匹配成功,返回k 否则匹配失败,返回0

时间复杂度：设匹配成功发生在si处，则在i-1趟不成功的匹配中比较了（i-1）m次，第i趟成功匹配共比较了m次，所以总共比较了im次，因此平均比较次数是：

pi(im)=

(im)=

一般情况下，m<实现过程：在串S和串T中高比较的起始下标i和j；循环直到S中所剩字符小于T的长度或T的所有字符均比较完（如果S[i]=T[j],则继续比较S和T的下一个字符；否则将j向右滑动到next[j]位置，即j=next[j];如果j=0,则将i和j分别+1，准备下趟比较，至于其中的next在此不作详细讲解）；如果T中所有字符均比较完，则匹配成功，返回匹配的起始下标；否则匹配失败，返回0。 时间复杂度：Ο(nm)，当m<C++，运行环境Microsoft Visual C++ 6.0 五、实验过程的原始记录 BF算法 程序代码

#include #include void main() {

cout<<\"请输入主串并且以0和回车结束\"<for(int m=0;m<100;m++) {

cin>>s[m]; if(s[m]=='0') {

s[m]='\\0'; break; } }

cout<<\"您输入的主串为：\"; for(int o=0;ocout<cout<cout<<\"主串长度：\"; cout<cout<<\"请输入子串并且以0和回车结束\"<cin>>t[n]; if(t[n]=='0') {

t[n]='\\0'; break; } }

cout<<\"您输入的子串为：\"; for(int a=0;acout<cout<cout<<\"子串长度：\"; cout<cout<int i,j,k,y=0;

for(i=0;ik=i;

for(j=0;j{

if(s[i]==t[j]) {

if(j==strlen(t)-1) {

cout<<\"找到了相同的字串：\";

cout<<\"位置在主串的第\"<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<<\"没有找到可以匹配的子串\"<程序执行结果：

查找到了子串 没有查找到子串

KMP算法 程序代码

#include #include

//前缀函数值,用于KMP算法 int GETNEXT(char t[],int b) { int NEXT[10]; NEXT[0]=-1; int j,k; j=0; k=-1; while(jint KMP(char s[],char t[]) { int a=0; int b=0; int m,n; m=strlen(s); //主串长度 n=strlen(t); //子串长度 cout<if(b==n) { cout<<\"找到了相应的子串位置在主串：\"<void main() {

cout<<\"请输入主串并且以0和回车结束\"<>s[m]; if(s[m]=='0') { s[m]='\\0'; break; } } cout<<\"您输入的主串为：\"; for(int o=0;o>t[n]; if(t[n]=='0') { t[n]='\\0'; break;

} }

cout<<\"您输入的子串为：\"; for(int a=0;acout<cout<<\"子串长度：\"; cout<}

程序执行结果：

查找到子串

没有查到子串