字符串匹配算法报告

课程设计报告题目：字符串匹配算法实测分析课程名称：数据结构专业班级：计科XX学号：UXXXXXXX姓名：FSH指导教师：xxx报告日期：2015.9.13计算机科学与技术学院数据结构课程组2015年5月题目字符串匹配算法实测分析设计目的：掌握线性结构中的字符串的物理存储结构与基本算法，通过查询阅读文献资料，拓广知识面以及培养学生科研能力。设计内容：结合教材上的字符串匹配算法，查询文献资料检索4种以上的有关精确匹配算法，掌握算法原理并实现。设计要求：（1）查阅相关的文献资料，特别是留意年近些年发表的文献资料；（2）要求对各种算法进行理论分析，同时也对实测结果进行统计分析。测试数据要求有一定规模，比如一本书或不少于50篇的中英文文献。（3）要求界面整洁、美观，操作方便；报告内容：（一）,运行界面，及运行结果截图（二）,各算法的具体分析，包括起源，基本思路，实例分析，具体实现，和本算法代码。（三），总程序源代码。（四），课程设计心得（一）,运行界面，运行结果说明：运行代码显示界面：对于S串可以手动输入字符串检索，也可以选择在计算机里建好的TXT文件，按任意键退出。按2确认，键入一本书的TXT文件，运行如下输入待搜索子串“史记”得到运行结果，各算法均返回子串在母串出现的位置执行算法得运行结果，返回子串在母串所有出现位置。结果显示运行时间用以统计时间效率：另一段检索结果的时间截图结果显示如下：（二）,各算法的具体分析一．穷举算法（Bruteforce）算法：.1.算法起源：此算法思路简单，容易想到，没有确定的提出者‘2．算法基本思想：之所以成为穷举法，即如名字所言，逐个比较直至穷尽/结束，基本思路为：假设S为母字符串，长度为lengthS，T为子字符串，长度为lengthT.则从母串第i位元素（从第一位i=1元素开始）开始一次提取长度为lengthT的一串字符挨个与S字符串比较是否相等，若相等，则匹配成功并输出i,然后在S上后移一位继续比较，直至比较完整个S.slidingwindow：3．案例分析：假设母串S:edgoodbnbqgoodewuopimmxccaluhfui子串T:goodboyN=lengthS–length+1(edgoodb不等于goodboy且iN，i+1即后移一位比较)(dgoodbo不等于goodboy且iN，i+1即后移一位比较)(goodboy等于goodboy且iN，匹配成功，输出i，后移一位比较)......(i!N，字符相等，输出i；字符不等，结束i；4.算法具体实现：字符串的物理存储实现—malloc函数申请空间返回unsignedchar型指针，线性结构；设置参数:i,用以表示检测位，范围为（1，N）用for循环语句判断是否遍历S字符串。其中N=lengthS–length+1；辅助函数：Substring（S,i，n）作用为提取S字符串里从第i位起长度为n的字符串，其返回值为unsignedchar型指针。Substring算法：edgoodboybnbqgoodewuopimmxccaluhfuiedgoodbdgoodbogoodboyaluhfuistatussubstring(strings,intpose,intlen)//子字符串提取函数substring；返回值为子str字符串{unsignedchar*sub;sub=malloc(10000*sizeof(unsignedchar));inti=strlen(s);intk=pose+len-1;if(i0||posei||ki)returnNULL;inta;for(a=0;alen;a++,pose++)sub[a]=s[pose-1];sub[a]='\0';returnsub;}5.算法源码：voidindex(strings,stringt){intm,n,i;stringtest;test=malloc(10000*sizeof(unsignedchar));n=strlen(s);m=strlen(t);i=1;inta=0;intjishu[1000];//数组用来计数匹配成功的位置printf(\n穷举算法运行得：\n);while(i=n-m+1){strcpy(test,substring(s,i,m));if(strcmp(test,t)!=0)++i;else{jishu[a]=i;printf(匹配成功输出:%d\n,jishu[a]);++i;++a;}//返回子串在主串中的位置}//while//S中不存在与T相等的子串}//Index6.效率分析：穷举算法虽然易于理解，也容易实现，但是效率却比较低下，因为该算法对于S字符串上的前N位元素，每个元素都提取字符串并进行挨个比较，比较完全匹配或者出现失配时后移一位继续比较，若S长度m，T长度n,则找到所有匹配位置的时间O(mn)。二．Sundy算法：1.起源：Sunday算法是DanielM.Sunday于1990年提出的字符串模式匹配。其核心思想是：在匹配过程中，模式串发现不匹配时，算法能跳过尽可能多的字符以进行下一步的匹配，从而提高了匹配效率。2.算法基本思想：从母串S提取比较字符串，用T字符串的最后一位元素t[n-1]与s[i-1]比较，出现不相时运用sundy核心算法，即坏字符算法。坏字符即为s[i-1]，然后再在T中找有无坏字符，方向为从前往后，若找到则把该位移到和S的坏字符对齐，若没找到，则后移长度为T串长，在提取比较是否相等，若相等输出在S上的位置i，若不等但t[n-1]与s[i-1]，则后移一位继续比较，直至走完S串。3.案例分析：假设母串S:edgoodbnbqgoodadecmnkdewuopimmxccaluhfui若子串为T1:akideb假设已经比较到第3位若子串为T2:adulgnd假设已比较到第19位假设已比较到第19位：(T1未找到坏字符n，后移6个字符)（在T中找到坏字符U，平移7–2—1=4）edgoodbnbqgooafsffweddadecmnkdewuopimmxccaluhadulgndakidebakidebadulgnd然后继续比较，如果出现匹配或者遇到非坏字符，则后移一位。4.算法具体实现：字符串的物理存储实现—malloc函数申请空间返回unsignedchar型指针，线性结构；设置参数:i,用以表示检测位，范围为（lengthT，lengthS）用for循环语句判断是否走完S字符串。辅助函数：Substring（S,i，n）作用为提取S字符串里从第i位起长度为n的字符串，其返回值为unsignedchar型指针。同穷举算法；5.算法源码：statussundy(strings,stringt){intm,n;//母子串长度+1m=strlen(s);n=strlen(t);inti=n;//检索总长变量n-mintb,bz;//坏字符在母子串位子intshift=0;//应该移动长度intsuf;//好字符长度intk;//计数unsignedchar*sub1;sub1=malloc(2000*sizeof(unsignedchar));printf(\nSUNDY算法运行得：);for(;i=m;i=i+shift)//判断母串是否检测完{strcpy(sub1,substring(s,i-n+1,n));if(strcmp(sub1,t)==0)printf(\n匹配成功,在母串的第%d个字符,i-n+1);intflag=1;//用来辅助跳出嵌套外循环{//shift函数外围开始if(strcmp(sub1,t)!=0){//shift函数范围开始if(t[n-1]!=s[i-1])//坏字符算法{for(k=0;kn&&flag;k++)//在子串中找坏字符{if(t[k]==s[i-1])//找到,跳出循环for{shift=n-k-1;flag=0;break;}if(k==n-1&&t[k]!=s[i-1]){shift=n;flag=0;break;}}//printf(\n坏字符时移动的距离为%d\n,shift);}}elseshift=1;//匹配成功，后移一位；}//shift外围函数}//for函数结束return0;}6.效率分析：此算法时间复杂度明显要优于穷举算法，因为穷举算法要挨个移动比较字符串，而该算法可能一次移动多个距离，继而会缩短时间，提高效率。而且当子字符串T越长，所含元素差异越大，效率就会越高,因为此时T串内更容易遇到好字符，而且T越长移动距离约长。三.cloudy算法：1.算法起源：提出者和时间不确定2.算法基本思想：算法先比较T串和对应S提取串中后面元素，先比较最后一个元素，如果串不等时最后元素不等或者字符串匹配（此时输出i），则后移一位继续比较，若最后一个元素相等则开始好后缀算法核心思路：在比较倒数第二个元素是否相等，依次往前，假设最后相等长度为m,则在T串内从前向后查找是否有和后m位相等的短串，若未找到，则在T内从前向后找有无和后m-1长度的字符串，找到后以此为与T后面对应元素字符距离差为移动距离，继而得到好后缀算法。3.案例分析：假设母串S:edgoodbnbqgoodadecmnkdewuopimmxccaluhfui若子串为T1:cnkdmnk假设已经比较到第15位在第15位时母串待匹字符串adecmnk,而子串cnkdmnk,后三位相同,为mnk此时从T串寻找，发现没有mnk然后寻找发现前面有nk,而此nk和T内后nk相差4位，故而得到应该后移4位，然互继续比较，如此循环直到结束。4.算法具体实现：字符串的物理存储实现—malloc函数申请空间返回unsignedchar型指针，线性结构；设置参数:i,用以表示检测位，范围为（lengthT，lengthS）用for循环语句判断是否走完S字符串。辅助函数：Substring（S,i，n）作用为提取S字符串里从第i位起长度为n的字符串，其返回值为unsignedchar型指针。同穷举算法；edgoodbnbqgoodadecmnkdewuopimmxccaluhfuicnkdmnkcnkdmnk5.算法源码：statuscloudy(strings,stringt){intm,n;//母子串长度+1m=strlen(s);n=strlen(t);inti=n;//检索总长变量n-mintb,bz;//坏字符在母子串位子intshift=0;//应该移动长度intsuf;//好字符长度unsignedchar*sub1;sub1=malloc(10000*sizeof(unsignedchar));printf(\nCLOUDY算法运行得：);for(;i=m;i=i+shift)//判断母串是否检测完{strcpy(sub1,substring(s,i-n+1,n));if(strcmp(sub1,t)==0){printf(\n匹配成功,在母串的第%d个字符,i-n+1);shift=1;}/*printf(\n输出sub1字符串：\n);for(i=0;istrlen(sub1);i++)printf(%c,sub1[i]);//输出sub11字符串printf(\n);*/{//shift函数外围开始if(strcmp(sub1,t)!=0){//shift函数范围开始if(t[n-1]!=s[i-1])//坏字符算法shift=1;else//好后缀{inta=0,g=1;//g为好后缀个数for(a;an;a++){if(t[n-a-2]==s[i-a-2]){++g;}elsebreak;}//printf(\n输出好后缀字符个数%d,g);//寻找好前缀：//用来求得shiftginth;intshift=-1;//初始值，用来判断后面stringtest;stringgood;test=malloc(10000*sizeo