算法设计_B10040101

-算法与数据结构设计报告（2011/2012学年第二学期）题目：模式匹配算法的设计与实现专业计算机科学与技术学生姓名王欣源班级学号B10040101指导教师肖甫指导单位计算机科学与技术系日期2012年6月1日-评分细则评分项优秀良好中等差遵守机房规章制度上机时的表现学习态度程序准备情况程序设计能力团队合作精神课题功能实现情况算法设计合理性用户界面设计报告书写认真程度内容详实程度文字表达熟练程度回答问题准确度简短评语教师签名：年月日评分等级备注评分等级有五种：优秀、良好、中等、及格、不及格-一．课题名称：模式匹配算法的设计与实现设计要求：理解模式匹配的含义，掌握简单匹配算法及模式匹配KMP算法的思想，实现以下任务：（1）编程动态实现简单模式匹配算法及模式匹配KMP算法；（2）根据给定的主串与模式串，给出根据两种匹配算法进行匹配的各趟匹配结果；（3）测试用例：主串：ThrougharetrospectivelookatthemathematicsteachingatUSTC,thisarticlesummarizesuniversity’steachingachievementsinpast45years.匹配子串：teaching输出结果：匹配子串teaching出现在主串中的次数为22次的匹配的位置分别是：48104;(4)一个应用实例如下：要求编写建立一个文本文件，每个单词不包括空格且不跨行，单词由字符序列构成，且区分大小写；统计给定单词在文本中出现的总次数；检索出某个单词在文本中的行号、在该行中出现的次数及位置。二．课题内容和要求本题主要是要掌握模式匹配的含义，以及KMP模式匹配算法相比简单模式匹配算法优越性。模式匹配是指有两个串S和P，在串S中找P的过程。其中S是主串，P是模式串。简单匹配算法是从主串S中下标i的字符与模式串P的第1个字符开始逐个比较，遇到不相等时，即达到失配点，该趟匹配失败，S回到原来的i+1的位置，P回到第1个字符位置，继续下一趟匹配，直到匹配成功。简单模式匹配算法效率不高，原因在于匹配过程中有回溯。而KMP算法中，i只进不退，对串S来说就消除了回退。本课题要求用简单模式匹配和KMP模式匹配分别来测试用例：ThrougharetrospectivelookatthemathematicsteachingatUSTC,thisarticlesummarizesuniversity’steachingachievementsinpast45years.其中模式串是:teaching,经过测试后都应该-得到的结果是：匹配子串teaching出现在主串中的次数为2，2次的匹配的位置分别是：46102;如果加入一个能计算时间的函数后，应该得到的结果是用简单模式匹配的时间比KMP模式匹配运行的时间长。由此，就可以得到在测试样例较多的情况下选用算法会节省时间，这对一些项目来说是很重要的，就突出了KMP算法的优越性。在课题要求中的应用实例中，要求1.建立一个文本文件，要求编写建立一个文本文件，每个单词不包括空格且不跨行，单词由字符序列构成，且区分大小写；2.编写程序能够读入文本文件中的内容,运用已经写好的程序统计给定单词在文本中出现的总次数；3.能够检索出某个单词在文本中的行号、在该行中出现的次数及位置。KMP算法也有优化的地方。在此，我又将改进的KMP算法也写进去了，三种方法可以放在一起比较，找出最优化的算法。三．需求分析1.实现简单模式匹配的函数，其中公有函数Find(String&p)调用私有函数Find(inti,String&p),私有函数每次在主串中找出一个模式串，而公有函数可以计算出所有的模式串的个数和位置。intString::Find(inti,String&P)//代码具体见详细设计intString::Find(String&P)//代码具体见详细设计2.实现KMP模式匹配的函数，其中公有函数KMPFind(String&p)调用私有函数KMPFind(inti,String&p),私有函数每次在主串中找出一个模式串，而公有函数可以计算出所有的模式串的个数和位置。intString::KMPFind(inti,String&P)//代码具体见详细设计intString::KMPFind(String&P)//代码具体见详细设计3.实现改进的KMP模式匹配的函数，其中公有函数KMPFindImprove(String&p)调用私有函数KMPFindImprove(inti,String&p),私有函数每次在主串中找出一个模式串，而公有函数可以计算出所有的模式串的个数和位置。intString::KMPFindImprove(inti,String&P)//代码具体见详细设计intString::KMPFindImprove(String&P)//代码具体见详细设计4.经过比较后改进的KMP算法是最优化的，所以在读取文件、测试文件时采用该进的KMP算法来做。其中取文件的函数Read()要自己设计voidString::Read(char*file)//代码具体见详细设计5.main（）函数中做了一个菜单，可以根据不同的选择测试不同的功能。-四．设计概要1．程序的算法设计说明，采用流程图形式2.每个程序中使用的存储结构设计说明因为采用的是面向对象C++的方法，定义了一个String类，其String类中成员变量和成员函数原型声明如下：classString{Private：intn;1.简单模式匹配做测试样例2.KMP模式匹配做测试样例4．从文本读入并且测试5．返回调用find函数调用kmpfind函数调用kmpfindImprov函数3.改进的KMP模式匹配做测试样例调用kmpfindImprov函数结束开始-char*str;int*count;//记录子串在主串中出现的位置intFind(inti,String&P);//简单匹配算法找到最近的匹配串后立即停止，而不向下继续且缺乏一个数组记录位置intfail();//记录失败函数voidFail();intKMPFind(inti,String&P);voidImproveFail();//改进的失败函数intKMPFindImprove(inti,String&P);public:String();//建立一个空串String(constchar*p);String(constString&p);//拷贝函数~String();intLength(){returnn;};//返回当前串对象长度voidOutput(){coutstr;};//输出字符串intFind(String&P);//简单匹配算法intKMPFind(String&P);//KMP匹配算法intKMPFindImprove(String&P);//改进的KMP匹配算法voidOutput2();//输出子串在主串中出现的位置voidOutput3();//输出子串所在行数，位置及总个数voidRead(char*);};各个功能段均采用数组的存储结构。五．详细设计#includeiostream#includestring#includefstream#includecstdlib#includetime.husingnamespacestd;#defineMAX100000#defineM69classString{private:intn;char*str;int*count;//记录子串在主串中出现的位置intFind(inti,String&P);//简单匹配算法找到最近的匹配串后立即停止，而不向下继续且缺乏一个数组记录位置int*f();//记录失败函数voidFail();intKMPFind(inti,String&P);//改进的失败函数-voidImproveFail();intKMPFindImprove(inti,String&P);public:String();//建立一个空串String(constchar*p);String(constString&p);//拷贝函数~String();intLength(){returnn;};//返回当前串对象长度voidOutput(){coutstr;};//输出字符串intFind(String&P);//简单匹配算法intKMPFind(String&P);//KMP匹配算法intKMPFindImprove(String&P);//改进的KMP匹配算法voidOutput2();//输出子串在主串中出现的位置voidOutput3();//输出子串所在行数，位置及总个数voidRead(char*);};String::String()//无参数的构造函数进行初始化{n=0;str=NULL;count=NULL;f=NULL;}String::String(constchar*p)//有参数的构造函数{n=strlen(p);str=newchar[n+1];strcpy(str,p);count=newint[n];for(inti=0;in;i++)count[i]=0;f=newint[n];for(intj=0;jn;j++)f[j]=-1;}String::String(constString&p)//拷贝构造函数{n=p.n;str=newchar[n+1];if(str==NULL)exit(1);for(inti=0;in;i++)str[i]=p.str[i];str[n]='\0';//结束标识符'\0'，否则会出现乱码count=newint[n];for(intj=0;jn;j++)-count[j]=p.count[j];f=newint[n];for(intk=0;kn;k++)f[k]=p.count[k];}String::~String(){delete[]str;}intString::Find(inti,String&P)//简单匹配算法i为主串P的位置，开始置0{if(i0||in-1)//越界检查{coutOutofbounds!endl;return-1;}char*pp=P.str;//模式串指针pp指向第一个字符char*t=str+i;//主串指针t指向下标i的字符while(*pp!='\x0'&&i=n-P.n)//子串pp未到串尾且剩余字符超过模式串长，则循环{if(*pp++!=*t++){pp=P.str;//模式串回到第一个字符t=str+(++i);//主串回到i+1的位置}}if(*pp=='\0')returni;//若pp已到串尾，则匹配成功return-1;}intString::Find(String&P){intsum=0;intj=Find(0,P);//共有find函数调用私有函数findwhile(j!=-1){count[sum]=j;sum++;//count记录位置，sum记录次数if(j=n-P.n)j=Find(j+P.n,P);}returnsum;}voidString::Fail()//失败函数{-intj=0,k=-1;f[0]=-1;while(jn){if((k==-1)||(str[j]==str[k])){j++;k++;//k==-1或str[j]==str[k]时，j,k各扩展1位，j无回溯f[j]=k;//求得的k存入f[j]}elsek=f[k];//str[j]不等于str[k]时，k回溯到f[k]}}intString::KMPFind(inti,String&P){if(i0||in-1)//越界检查{coutOutofbounds!endl;return-1;}this-Fail();intj=0,m=P.n;while(in&&jm){if(j==-1||str[i]==P