《计算机算法实验报告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);程序执行结果：查找到子串 没有查到子串
