《计算机算法实验报告bf和kmp》由会员分享,可在线阅读,更多相关《计算机算法实验报告bf和kmp(7页珍藏版)》请在金锄头文库上搜索。
1、天津市大学软件学院实验报告课程名称:串匹配算法实验姓名: 陈小龙 学号:1150210403班级: 业务 1114 串匹配问题一、实验题目:给定一个主串,在该主串中查找并定位任意给定字符串。二、实验目的:(1)深刻理解并掌握蛮力法的设计思想;(2)提高应用蛮力法设计算法的技能;(3)理解这样一个观点:用蛮力法设计的算法,一般来说,经过适度的努力后,都可以对算法的第一个版本进行一定程度的改良,改进其时间性能。三、实验分析:串匹配问题的 BF 算法1 在串 S 中和串 T 中设比较的下标 i=1 和 j=1; 2 循环直到 S 中所剩字符个数小于 T 的长度或 T 中所有字符均比较完2.1 k=i
2、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 次,所以总共比较了 i m 次,因此平 均比较次数是:pi (i m)= (i m)=+1=1 +1=11+1 (+2)2一般情况下,m#includevoid main()coutsm;if(sm=0)sm=0;break;couttn;if(tn=0)tn=0;break;cout#include/前缀函数值,用于 KMP 算法int GETNEXT(char t,int b)int NEXT10;NEXT0=-1;int j,k;j=0;k=-1;while(jsm;if(sm=0)sm=0;break;couttn;if(tn=0)tn=0;break;cout您输入的子串为:;for(int a=0;astrlen(t);+a)coutta;coutendl;cout子串长度:;coutstrlen(t);coutendl;KMP(s,t);程序执行结果:查找到子串 没有查到子串