蛮力法解决串匹配问题.doc

算法分析实验报告蛮力法-串匹配问题学生姓名： 专 业： 班 级： 学 号: 指导教师： 2017年6月12日目录一、实验题目2二、实验目的2三、实验要求2四、实现过程31、实验设计：32、调试分析：83、运行结果：94、实验总结：9五、参考文献10一、实验题目蛮力法-串匹配问题二、实验目的(1)深刻理解并掌握蛮力法的设计思想；(2)提高应用蛮力法设计算法的技能；(3)理解这样一个观点：用蛮力法设计的算法，一般来说，经过适度的努力后，都可以对算法的第一个版本进行一定程度的改良，改进其时间性能。三、实验要求1.问题描述：给定两个字符串S和T，在主串S中查找子串T的过程称为串匹配，T称为模式。设主串S=“abcabcacb”,模式=“abcac”。2.算法：蛮力法：蛮力法（也称穷举法或枚举法）是一种简单直接的解决问题的方法，常常直接基于问题的描述，所以，蛮力法也是最容易应用的方法，例如，对于给定的整数a和非负整数n，计算an的值，最直接最简单的方法就是把1和a相乘n次，即：an=a*a*a*a。 蛮力法所依赖的基本技术是遍历（也称扫描），即采用一定的策略依次处理待求解问题的所有元素，从而找出问题的解。依次处理所有元素是蛮力法的关键，为了避免陷入重复试探，应保证处理过的元素不再被处理。用蛮力法设计的算法，一般来说，都可以对算法的第一个版本进行一定程度的改进，提高其时间性能，但只能减少系数，而数量级不会改变。四、实现过程1、实验设计：l 想法一：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次，所以总共比较了i*m次，因此平均比较次数是： 一般情况下，mn,因此最坏情况下时间复杂度是(n*m)。l 想法二：KMP算法实现过程：在串S和串T中高比较的起始下标i和j；循环直到S中所剩字符小于T的长度或T的所有字符均比较完（如果Si=Tj,则继续比较S和T的下一个字符；否则将j向右滑动到nextj位置，即j=nextj;如果j=0,则将i和j分别+1，准备下趟比较，至于其中的next在此不作详细讲解）；如果T中所有字符均比较完，则匹配成功，返回匹配的起始下标；否则匹配失败，返回0。 时间复杂度：当m=1;len-)for(i=0;ilen;i+)if(Ti != Tj-len+i) break;if(i=len)nextj=len; break;if(len1) nextj=0;int KMP(char S,char T)int i=0,j=0;int next80;GetNext(T,next);while(Si != 0& Tj != 0)if(Si=Tj)i+;j+;elsej=nextj;if(j=-1)i+;j+;if(Tj=0)return (i-strlen(T)+1);else return 0;2、运行结果：3、实验总结： 本次实验的学习进一步对蛮力法的理解，同时对数据结构的一些算法有更深的掌握，同时认识到自己对某些基础算法掌握的并不是很牢固，要加强自己的动手实践能力！五、参考文献1 王红