算法设计_B10040101.doc

算法与数据结构设计报告（ 2011 / 2012 学年 第 二 学期）题 目： 模式匹配算法的设计与实现 专 业 计算机科学与技术 学 生 姓 名 王欣源 班 级 学 号 B10040101 指 导 教 师 肖甫 指 导 单 位 计算机科学与技术系 日 期 2012年6月1日 评 分 细 则评分项优秀良好中等差遵守机房规章制度上机时的表现学习态度程序准备情况程序设计能力团队合作精神课题功能实现情况算法设计合理性用户界面设计报告书写认真程度内容详实程度文字表达熟练程度回答问题准确度简 短 评 语教师签名： 年 月 日评分等级备注评分等级有五种：优秀、良好、中等、及格、不及格一课题名称：模式匹配算法的设计与实现 设计要求：理解模式匹配的含义，掌握简单匹配算法及模式匹配KMP算法的思想，实现以下任务：（1）编程动态实现简单模式匹配算法及模式匹配KMP算法；（2）根据给定的主串与模式串，给出根据两种匹配算法进行匹配的各趟匹配结果；（3）测试用例：主串：Through a retrospective look at the mathematics teaching at USTC, this article summarizes universitys teaching achievements in past 45 years.匹配子串：teaching输出结果：匹配子串 teaching 出现在主串中的次数为 22 次的匹配的位置分别是：48 104;(4)一个应用实例如下：l 要求编写建立一个文本文件，每个单词不包括空格且不跨行，单词由字符序列构成，且区分大小写；l 统计给定单词在文本中出现的总次数；检索出某个单词在文本中的行号、在该行中出现的次数及位置。 二 课题内容和要求本题主要是要掌握模式匹配的含义，以及KMP模式匹配算法相比简单模式匹配算法优越性。模式匹配是指有两个串S和P，在串S中找P的过程。其中S是主串，P是模式串。简单匹配算法是从主串S中下标i的字符与模式串P的第1个字符开始逐个比较，遇到不相等时，即达到失配点，该趟匹配失败，S回到原来的i+1的位置，P回到第1个字符位置，继续下一趟匹配，直到匹配成功。简单模式匹配算法效率不高，原因在于匹配过程中有回溯。而KMP算法中，i只进不退，对串S来说就消除了回退。本课题要求用简单模式匹配和KMP模式匹配分别来测试用例：Through a retrospective look at the mathematics teaching at USTC, this article summarizes universitys teaching achievements in past 45 years.其中模式串是:teaching,经过测试后都应该得到的结果是：匹配子串 teaching 出现在主串中的次数为 2，2 次的匹配的位置分别是：46 102;如果加入一个能计算时间的函数后，应该得到的结果是用简单模式匹配的时间比KMP模式匹配运行的时间长。由此，就可以得到在测试样例较多的情况下选用算法会节省时间，这对一些项目来说是很重要的，就突出了KMP算法的优越性。在课题要求中的应用实例中，要求1.建立一个文本文件，要求编写建立一个文本文件，每个单词不包括空格且不跨行，单词由字符序列构成，且区分大小写；2.编写程序能够读入文本文件中的内容,运用已经写好的程序统计给定单词在文本中出现的总次数；3.能够检索出某个单词在文本中的行号、在该行中出现的次数及位置。KMP算法也有优化的地方。在此，我又将改进的KMP算法也写进去了，三种方法可以放在一起比较，找出最优化的算法。三 需求分析1.实现简单模式匹配的函数，其中公有函数Find(String &p)调用私有函数 Find(inti,String &p),私有函数每次在主串中找出一个模式串，而公有函数可以计算出所有的模式串的个数和位置。int String:Find(int i,String &P) / 代码具体见详细设计int String:Find(String &P) /代码具体见详细设计2. 实现KMP模式匹配的函数，其中公有函数KMPFind(String &p)调用私有函数 KMPFind(inti,String &p),私有函数每次在主串中找出一个模式串，而公有函数可以计算出所有的模式串的个数和位置。int String:KMPFind(int i,String &P) / 代码具体见详细设计int String:KMPFind(String &P) /代码具体见详细设计3.实现改进的KMP模式匹配的函数，其中公有函数KMPFindImprove(String &p)调用私有函数KMPFindImprove(inti,String &p),私有函数每次在主串中找出一个模式串，而公有函数可以计算出所有的模式串的个数和位置。int String:KMPFindImprove(int i,String &P) / 代码具体见详细设计int String:KMPFindImprove(String &P) /代码具体见详细设计 4.经过比较后改进的KMP算法是最优化的，所以在读取文件、测试文件时采用该进的KMP算法来做。其中取文件的函数Read()要自己设计void String:Read(char *file) /代码具体见详细设计 5.main（）函数中做了一个菜单，可以根据不同的选择测试不同的功能。四 设计概要1 程序的算法设计说明，采用流程图形式1.简单模式匹配做测试样例2.KMP模式匹配做测试样例4从文本读入并且测试5返回调用find函数调用kmpfind函数调用kmpfindImprov函数3.改进的KMP模式匹配做测试样例调用kmpfindImprov函数结束开始2. 每个程序中使用的存储结构设计说明 因为采用的是面向对象C+的方法，定义了一个String类，其String类中成员变量和成员函数原型声明如下：class StringPrivate：int n;char *str;int *count; /记录子串在主串中出现的位置 int Find(int i,String &P); / 简单匹配算法 找到最近的匹配串后立即停止，而不向下继续且缺乏一个数组记录位置int fail(); /记录失败函数void Fail(); int KMPFind(int i,String &P); void ImproveFail(); /改进的失败函数int KMPFindImprove(int i,String &P); public:String(); /建立一个空串String(const char *p);String(const String &p); /拷贝函数String();int Length() return n; /返回当前串对象长度void Output() coutstr; /输出字符串int Find(String &P); /简单匹配算法int KMPFind(String &P); /KMP匹配算法 int KMPFindImprove(String &P); /改进的KMP匹配算法 void Output2(); /输出子串在主串中出现的位置void Output3(); /输出子串所在行数，位置及总个数 void Read(char *);各个功能段均采用数组的存储结构。五详细设计#include#include#include#include#includeusing namespace std;#define MAX 100000#define M 69class Stringprivate:int n;char *str;int *count; /记录子串在主串中出现的位置 int Find(int i,String &P); / 简单匹配算法 找到最近的匹配串后立即停止，而不向下继续且缺乏一个数组记录位置 int *f (); /记录失败函数void Fail(); int KMPFind(int i,String &P); /改进的失败函数 void ImproveFail();int KMPFindImprove(int i,String &P); public:String(); /建立一个空串String(const char *p);String(const String &p); /拷贝函数String();int Length() return n; /返回当前串对象长度void Output() coutstr; /输出字符串int Find(String &P); /简单匹配算法int KMPFind(String &P); /KMP匹配算法 int KMPFindImprove(String &P); /改进的KMP匹配算法 void Output2(); /输出子串在主串中出现的位置void Output3(); /输出子串所在行数，位置及总个数 void Read(char *);String:String() /无参数的构造函数 进行初始化n=0;str=NULL;count=NULL;f=NULL;String:String(const char *p)/有参数的构造函数n=strlen(p);str=new charn+1;strcpy(str,p);count=new intn;for(int i=0;in;i+)counti=0;f=new intn;for(int j=0;jn;j+)fj=-1;String:String(const String &p) /拷贝构造函数n=p.n;str=new charn+1;if(str=NULL) exit(1);for(int i=0;in;i+)stri=p.stri;strn=0; /结束标识符0，否则会出现乱码 count=new intn;for(int j=0;jn;j+)countj=p.countj;f=new intn;for(int k=0;kn;k+)fk=p.countk;String:String()delete str;int String:Find(int i,String &P) / 简单匹配算法 i为主串P的位置，开始置0if(in-1) /越界检查coutOut of bounds!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)return i; /若pp已到串尾，则匹配成功return -1;int String:Find(String &P) int sum=0; int j=Find(0,P); /共有find函数调用私有函数find while(j!=-1)countsum=j; sum+; /count记录位置，sum记录次数 if(j=n-P.n) j=Find(j+P.n,P); return sum;void String:Fail() /失败函数 int j=0,k=-1;f0=-1;while(jn)if(k=-1) | (strj=strk)j+; k+; /k=-1或strj=strk时，j,k各扩展1位，j无回溯fj=k; /求得的k存入fjelse k=fk; /strj不等于strk时，k回溯到fkint String:KMPFind(int i,String &P) if(in-1) /越界检查coutOut of bounds!Fail();int j=0,m=P.n;while(in & jm)if(j=-1 | stri=P.strj) /相等或j=-1时，i、j均后移1个位置i+; j+;elsej=P.fj; /到达失配点，j回溯到fjreturn (j=m)? i-m:-1);int String:KMPFind(String &P) int sum=0; int j=KMPFind(0,P); while(j!=-1)countsum=j; sum+; /count记录位置，sum记录次数 if(j=n-P.n) j=KMPFind(j+P.n,P); return sum;void String:ImproveFail() /改进的失败函数int j=0,k=-1; f0=-1;while(jn)if(k=-1) | (strj=strk) /当k=-1或strj=strk时，j,k各扩展1位j+;k+;if(strj=strk) /将字符pk与pj比较，若相等则将fk存入fjfj=fk;elsefj=k; /否则将k存入fjelsek=fk; /strj不等于strk时，k回溯到fk,j无回溯int String:KMPFindImprove(int i,String &P) if(in-1)coutOut of bounds!ImproveFail();int j=0,m=P.n;while(in & jm)if(j=-1 | stri=P.strj)i+;j+;elsej=P.fj;return (j=m)? i-m:-1);int String:KMPFindImprove(String &P) int sum=0; int j=KMPFindImprove(0,P); while(j!=-1) countsum+=j; if(j=n-P.n) j=KMPFindImprove(j+P.n,P); return sum; void String:Read(char *file) /通过文件读取char ch; char *temp=new charMAX;int i=0;ifstream infile(file); if(!file) /判断能否打开coutCannot open the file!endl;return;while(infile.get(ch)!=#) tempi+=ch;if(ch=#) /以#为结束标志break;tempi=0; n=i; str=new charn; /由于定义一个空子串时n=0,count,f等都为NULL,所以此处要重新定义 for(int z=0;zn;z+)strz=tempz;count=new intn;for(int k=0;kn;k+)countk=0;f=new intn; for(int j=0;jn;j+)fj=-1;infile.close();delete temp;void String:Output2() /输出子串在主串中的位置int i=0;while(counti!=counti+1 & iMAX-1) /若不再有新的子串匹配，则counti与counti+1均为0coutcounti ;i+;void String:Output3() /输出子串在文件中的行数、位置、及次数int i=0; int t=0;int *line=new intMAX; /记录字符串在该行出现的次数int *ram=new intM; /记录字符串在该行出现的位置for(int m=1;m=MAX;m+)linem=0;for(int n=1;n=M;n+)ramn=0;while(counti!=counti+1 & i0) |(l1=l2 & counti+1=0) /换行cout该单词在第l1行出现linel1次，分别在位置：;for(int s=0;st;s+)coutrams ; /每行中出现的位置coutendl;t=0;i+; /到下一行找void main()int choise=0; cout*; coutendl; cout*; coutendl; cout# 1.简单模式匹配做测试样例 #; coutendl; cout# 2.KMP模式匹配做测试样例 #; coutendl; cout# 3.改进的KMP模式匹配做测试样例 #; coutendl; cout# 4.从文本测试函数 #; coutendl; cout# 5.返回 #; coutendl; cout*; coutendl; cout*; coutchoise; if(choise=1) /简单模式匹配算法测试 clock_t start,finish; start=clock(); String s1(Through aretro spectivelook at the mathe matics teaching at USTC, this article summarizes universitys teaching achievements in past 45 years.); s1.Output(); coutendl; String s2(teaching); int m=s1.Find(s2); cout用简单模式匹配测匹配子串; s2.Output(); cout出现在主串中的次数为:mendl; if(m!=0) coutm次的匹配的位置分别是：;s1.Output2();coutendl; finish=clock(); coutendltime is:(double)(finish-start)/CLK_TCKendl; if(choise=2) /KMP模式匹配算法测试 clock_t start,finish; start=clock(); String s1(Through a retrospective look at the mathematics teaching at USTC, this article summarizes universitys teaching achievements in past 45 years.); s1.Output(); coutendl; String s2(teaching);cout用kmp模式匹配测匹配子串：; s2.Output(); coutendl; int n=s1.KMPFind(s2); cout出现在主串中的次数为:nendl; if(n!=0) coutn次的匹配的位置分别是：; s1.Output2(); coutendl; finish=clock(); coutendltime is:(double)(finish-start)/CLK_TCKendl; if(choise=3) /改进的KMP模式匹配算法