字符串匹配算法报告.docx

课程设计报告题目：字符串匹配算法实测分析课程名称：数据结构专业班级：计科XX学号：UXXXXXXX姓名：FSH指导教师：xxx报告日期：2015.9.13计算机科学与技术学院数据结构课程组2015年5月题目字符串匹配算法实测分析设计目的：掌握线性结构中的字符串的物理存储结构与基本算法通过查询阅读文献资料拓广知识面以及培养学生科研能力。设计内容：结合教材上的字符串匹配算法查询文献资料检索4种以上的有关精确匹配算法掌握算法原理并实现。设计要求：（1）查阅相关的文献资料特别是留意年近些年发表的文献资料；（2）要求对各种算法进行理论分析同时也对实测结果进行统计分析。测试数据要求有一定规模比如一本书或不少于50篇的中英文文献。（3）要求界面整洁、美观操作方便；报告内容：（一）运行界面及运行结果截图（二）各算法的具体分析包括起源基本思路实例分析具体实现和本算法代码。（三）总程序源代码。（四）课程设计心得（一）运行界面运行结果说明：运行代码显示界面：对于S串可以手动输入字符串检索也可以选择在计算机里建好的TXT文件按任意键退出。按2确认键入一本书的TXT文件运行如下输入待搜索子串“史记”得到运行结果各算法均返回子串在母串出现的位置执行算法得运行结果返回子串在母串所有出现位置。结果显示运行时间用以统计时间效率：另一段检索结果的时间截图结果显示如下：（二）各算法的具体分析一．穷举算法（Bruteforce）算法：.算法起源：此算法思路简单容易想到没有确定的提出者‘2．算法基本思想：之所以成为穷举法即如名字所言逐个比较直至穷尽/结束基本思路为：假设S为母字符串长度为lengthST为子字符串长度为lengthT.则从母串第i位元素（从第一位i=1元素开始）开始一次提取长度为lengthT的一串字符挨个与S字符串比较是否相等若相等则匹配成功并输出i然后在S上后移一位继续比较直至比较完整个S.slidingwindow：3．案例分析：假设母串S:edgoodbnbqgoodewuopimmxccaluhfui子串T:goodboyN=lengthS–length+1edgoodboybnbqgoodewuopimmxccaluhfuiedgoodb(edgoodb不等于goodboy且i<Ni+1即后移一位比较)dgoodbo(dgoodbo不等于goodboy且i<Ni+1即后移一位比较)goodboy(goodboy等于goodboy且i<N匹配成功输出i后移一位比较)......aluhfui(i!<N字符相等输出i；字符不等结束i；4.算法具体实现：字符串的物理存储实现—malloc函数申请空间返回unsignedchar型指针线性结构；设置参数:i用以表示检测位范围为（1N）用for循环语句判断是否遍历S字符串。其中N=lengthS–length+1；辅助函数：Substring（Sin）作用为提取S字符串里从第i位起长度为n的字符串其返回值为unsignedchar型指针。Substring算法：statussubstring(stringsintposeintlen)//子字符串提取函数substring；返回值为子str字符串{unsignedchar*sub;sub=malloc(10000*sizeof(unsignedchar));inti=strlen(s);intk=pose+len-1;if(i<0||pose>i||k>i)returnNULL;inta;for(a=0;a<len;a++pose++)sub[a]=s[pose-1];sub[a]='\0';returnsub;}5.算法源码：voidindex(strin