蛮力法解决串匹配问题

《蛮力法解决串匹配问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法分析实验报告蛮力法-串匹配问题学生姓名：专业：班级：学号:指导教师：2017年6月12日10目录一、实验题目2二、实验目的2三、实验要求2四、实现过程31、实验设计：32、调试分析：83、运行结果：94、实验总结：9五、参考文献1010一、实验题目蛮力法-串匹配问题二、实验目的(1)深刻理解并掌握蛮力法的设计思想；(2)提高应用蛮力法设计算法的技能；(3)理解这样一个观点：用蛮力法设计的算法，一般来说，经过适度的努力后，都可以对算法的第一个版本进行一定程度的改良，改进其时间性能。三、实验要求1.[问题描述]：给定两个字符串S和T，在主串S中查找子串T的过程称

2、为串匹配，T称为模式。设主串S=“abcabcacb”,模式=“abcac”。2.[算法]：蛮力法： 蛮力法（也称穷举法或枚举法）是一种简单直接的解决问题的方法，常常直接基于问题的描述，所以，蛮力法也是最容易应用的方法，例如，对于给定的整数a和非负整数n，计算an的值，最直接最简单的方法就是把1和a相乘n次，即：an=a*a*a*···*a。10蛮力法所依赖的基本技术是遍历（也称扫描），即采用一定的策略依次处理待求解问题的所有元素，从而找出问题的解。依次处理所有元素是蛮力法的关键，为了避免陷入重复试探，应保证处理过的元素不再被处理。用蛮力法设计的算法，一般来说，

3、都可以对算法的第一个版本进行一定程度的改进，提高其时间性能，但只能减少系数，而数量级不会改变。四、实现过程1、实验设计：l想法一：BF算法1在串S中和串T中设比较的下标i=1和j=1;2循环直到S中所剩字符个数小于T的长度或T中所有字符均比较完2.1k=i2.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次，所以总共比较了i*m次，因此平均

4、比较次数是：一般情况下，m<

5、位置si模式Ttj回溯第一趟匹配，i=4，j=4失败，i回溯到1，j回溯到010abcabcacb/00123456789abcac第二趟匹配，i=1,j=0失败，i回溯到2，j回溯到0abcabcacb/00123456789a第三趟匹配，i=2,j=0,失败，i回溯到3，j回溯到00123456789Abcabcacb/0a10第四趟匹配，i=8，j=5，T中全部字符都比较完毕，匹配成功Abcabcacb/0abcacl算法实现1）BFintBF(charS[],charT[],intindex){index=0;inti=0,j=0;while((S[i]

6、!='')&&(T[j]!='')){if(S[i]==T[j]){i++;j++;}else10{index++;i=index;j=0;}}if(T[j]=='')returnindex+1;elsereturn0;}2）KMPvoidGetNext(charT[],intnext[]){inti,j,len;next[0]=-1;for(j=1;T[j]!='';j++){for(len=j-1;len>=1;len--){for(i=0;i

7、[j]=len;break;10}}if(len<1)next[j]=0;}}intKMP(charS[],charT[]){inti=0,j=0;intnext[80];GetNext(T,next);while(S[i]!=''&&T[j]!=''){if(S[i]==T[j]){i++;j++;}else{j=next[j];if(j==-1){10i++;j++;}}}if(T[j]=='')return(i-strlen(T)+1);elsereturn0;}2、运行结果：3、实验总结：本次实验的学习进一步对蛮力法的理解，同时对数据结构的一

8、些算法有更深的掌握，同时