算法实验报告

《算法实验报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、学生学号2009210622实验课成绩算法实验报告实验课程名称算法设计与分析开课学院计算机科学与技术系指导老师姓名赵尔顿学生姓名贾少映学生专业班级计科09一班完成日期20112010—2011学年第一学期实验课程名称：算法设计与分析实验项目名称串匹配问题实验成绩实验者贾少映专业班级计科01班组别同组者实验日期年月日第一部分：实验分析与设计（可加页）一、实验内容描述（问题域描述）给定一个文本，在该文本中查找并定位任意给定的字符串。二．实验母的（1）深刻理解并掌握蛮力法的设计思想；（2）提高应用蛮力法设计算法的技能；（3）理解这样一个观点：用蛮力法设计的算法，一

2、般来说，经过适度的努力后，都可以对算法的第一个版本进行一定成都的改良，改进起时间性能。三．试验要求（1）实现BF算法；（2）实现BF算法的改进算法：KMP算法和BM算法（3）对上述3个师傅案发进行时间复杂性分析，并设计实验验证分析结果、实验基本原理与设计（包括实验方案设计，实验手段的确定，试验步骤等，用硬件逻辑或者算法描述）①　程序1伪代码：KMP算法伪代码：1.在串S和串TZ中分别设比较的起始下标i和j；2.循环知道S中所剩长度小雨T的长度或T中所有字符均比较完毕2.1如果S[i]=T[J],则继续比较S和T的下一个字符；否则2.2将j向右华东到next[

3、j]位置，即j=next[j];2.3如果j=0，则将i和j分别加1，准备下一趟比较；3.如果T中所有字符均比较完毕，则反悔匹配的起始下标，否则返回0；23时间复杂度分析：KMP算法的时间复杂性是O（m+n），当m《n时，KMP算法的时间复杂性是O(n)。程序源代码：#include#includeintnext[50];voidgetnext(charT[],intn);intmain(){chara[100],b[50];inti,j;intm,n;scanf("%s%s",a,b);m=strlen(a);n=st

4、rlen(b);getnext(b,n);i=j=0;while(i

5、

6、a[i]==b[j]){i++;j++;}elsej=next[j];if(j>=n)printf("%d",i-n);elseprintf("notfind");return0;}voidgetnext(charT[],intn){intk,j;next[0]=-1;k=0;j=1;while(j

7、

8、(T[j]==T[k])){k++;j++;next[j]=k;}elsek=next[k];}BF算法伪代码：1.在串S和串T中

9、设比较的起始下标i和j2.循环知道S中所剩字符个数小雨T的长度或T的所有字符均比较完2．1如果S[i]=T[j],则继续比较S和T的下一个字符，否则2.2将i和j回溯，准备下一趟比较；3.如果T中所有字符均比较完，则匹配成功，返回匹配的起始比较下标；否则匹配失败，返回0；算法复杂性分析:一般情况下，m《n，因此最坏情况下的时间复杂度是O(N*M);程序源代码：#includeusingnamespacestd;intmain(){inti,j,flag;chars[100],t[100];while(scanf("%s%s",s,t)!=

10、EOF){i=0;j=0;flag=0;while(i=strlen(t)){printf("%d",i-strlen(t));flag=1;break;}elsei=i-j+1,j=0;}if(!flag)printf("notfound");}return0;}BM算法：intbm(charS[],charT[],intn,intm){I=m;While(i<=n){j=m;While(j>0&&S[i]==T[j]){J=j-1;I=i

11、-1;}If(j==0)Returni+1;ElseI=i+dist(S[i]);}Return0;}程序源代码：#includeusingnamespacestd;intdist[200];chars[100],t[100];voidDist(chart[]){inti,k,j;k=strlen(t)-1;for(i=0;i<=26;i++){for(j=k;j>=0;j--)if(t[j]==i+'a'){dist[i+'a']=k-j;break;}if(j<0

12、

13、j==k)dist[i+'a']=k+1;for(j=k-1;j>=

14、0;j--)if(t[j]=='A'+i){dist