字符串匹配算法报告

课 程 设 计 报 告题目： 字符串匹配算法实测分析 课程名称： 数据结构 专业班级： 计科XX 学 号： UXXXXX XX 姓 名： FSH 指导教师： xxx 报告日期： 2015.9.13 计算机科学与技术学院数据结构课程组2015年5月题目 字符串匹配算法实测分析p 设计目的：掌握线性结构中的字符串的物理存储结构与基本算法，通过查询阅读文献资料，拓广知识面以及培养学生科研能力。p 设计内容：结合教材上的字符串匹配算法，查询文献资料检索4种以上的有关精确匹配算法，掌握算法原理并实现。p 设计要求：（1）查阅相关的文献资料，特别是留意年近些年发表的文献资料；（2）要求对各种算法进行理论分析，同时也对实测结果进行统计分析。测试数据要求有一定规模，比如一本书或不少于50篇的中英文文献。 （3）要求界面整洁、美观，操作方便；报告内容：（一）, 运行界面，及运行结果截图（二）,各算法的具体分析，包括起源，基本思路，实例分析，具体实现，和本算法代码。 （三），总程序源代码。 （四），课程设计心得（一）, 运行界面，运行结果说明：运行代码显示界面：对于S串可以手动输入字符串检索，也可以选择在计算机里建好的TXT文件，按任意键退出。 按2确认，键入一本书的TXT文件，运行如下 输入待搜索子串“史记”得到运行结果，各算法均返回子串在母串出现的位置执行算法得运行结果，返回子串在母串所有出现位置。结果显示运行时间用以统计时间效率：另一段检索结果的时间截图结果显示如下：（二）,各算法的具体分析一穷举算法（Brute force）算法： .1. 算法起源：此算法思路简单，容易想到，没有确定的提出者2 算法基本思想：之所以成为穷举法，即如名字所言，逐个比较直至穷尽/结束， 基本思路为：假设S为母字符串，长度为lengthS ，T为子字符串，长度为lengthT. 则从母串第i位元素（从第一位i=1元素开始）开始一次提取长度为lengthT的一串字符挨个与S字符串比较是否相等，若相等，则匹配成功并输出i ,然后在S上后移一位继续比较，直至比较完整个S.slidingwindow： 3案例分析： 假设母串S : edgoodbnbqgoodewuopimmxccaluhfui 子串T : goodboy N= lengthS length+1edgoodboybnbqgoodewuopimmxccaluhfui edgoodb(edgoodb不等于goodboy且iN，i+1即后移一位比较)dgoodbo (dgoodbo 不等于 goodboy且iN，i+1即后移一位比较)goodboy(goodboy 等于 goodboy且iN，匹配成功，输出 i ，后移一位比较) . . . . . .aluhfui (i!N，字符相等，输出i；字符不等，结束i； 4. 算法具体实现： 字符串的物理存储实现 malloc函数申请空间返回unsigned char 型指针，线性结构 ； 设置参数 : i, 用以表示检测位，范围为（1，N）用for循环语句判断是否遍历S字符串。其中N= lengthS length+1 ；辅助函数 ：Substring（S , i，n）作用为提取S字符串里从第i 位起长度为 n 的字符串 ，其返回值为unsigned char型指针。Substring算法：status substring( string s,int pose ,int len )/ 子字符串提取函数substring；返回值为子str字符串 unsigned char* sub; sub=malloc(10000*sizeof(unsigned char); int i=strlen(s); int k=pose+len-1; if(ii|ki) return NULL; int a; for( a=0;alen;a+,pose+) suba=spose-1; suba=0; return sub; 5 . 算法源码： void index(string s, string t)int m,n,i;string test;test=malloc(10000*sizeof(unsigned char);n=strlen(s);m=strlen(t);i=1;int a=0;int jishu1000;/数组用来计数匹配成功的位置 printf(n穷举算法运行得：n);while(i=n-m+1)strcpy(test,substring(s,i,m);if(strcmp(test,t)!=0) +i;else jishua=i; printf( 匹配成功输出:%dn,jishua); +i;+a; / 返回子串在主串中的位置 /while /S中不存在与T相等的子串/Index 6. 效率分析： 穷举算法虽然易于理解，也容易实现，但是效率却比较低下，因为该算法对于S字符串上的前N位元素，每个元素都提取字符串并进行挨个比较，比较完全匹配或者出现失配时后移一位继续比较，若S长度m，T长度n,则找到所有匹配位置的时间O(mn) 。 二Sundy算法：1. 起源：Sunday算法是Daniel M.Sunday于1990年提出的字符串模式匹配。其核心思想是：在匹配过程中，模式串发现不匹配时，算法能跳过尽可能多的字符以进行下一步的匹配，从而提高了匹配效率。 2.算法基本思想：从母串S提取比较字符串，用T字符串的最后一位元素tn-1与si-1比较，出现不相时运用sundy核心算法，即坏字符算法。 坏字符即为si-1，然后再在T中找有无坏字符，方向为从前往后，若找到则把该位移到和S的坏字符对齐，若没找到，则后移长度为T串长，在提取比较是否相等，若相等输出在S上的位置i，若不等但tn-1与si-1，则后移一位继续比较，直至走完S串。 3.案例分析：假设母串S : edgoodbnbqgoodadecmnkdewuopimmxccaluhfui若子串为T1 : akideb 假设已经比较到第3位 若子串为T2 :adulgnd 假设已比较到第19位 假设已比较到第19位：edgoodbnbqgooafsffweddadecmnkdewuopimmxccaluhfuiadulgndakidebadulgndakideb (T1未找到坏字符n，后移6个字符) （在T中找到坏字符U，平移7 21=4）然后继续比较，如果出现匹配或者遇到非坏字符，则后移一位。4. 算法具体实现： 字符串的物理存储实现 malloc函数申请空间返回unsigned char 型指针，线性结构 ； 设置参数 : i, 用以表示检测位，范围为（lengthT，lengthS）用for循环语句判断是否走完S字符串。辅助函数 ：Substring（S , i，n）作用为提取S字符串里从第i 位起长度为 n 的字符串 ，其返回值为unsigned char型指针。同穷举算法；5. 算法源码：status sundy(string s,string t) int m,n;/母子串长度+1 m=strlen(s); n=strlen(t); int i=n;/检索总长变量n-m int b,bz;/坏字符在母子串位子 int shift=0;/应该移动长度 int suf ;/好字符长度 int k;/计数 unsigned char* sub1; sub1=malloc(2000*sizeof(unsigned char); 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);int flag=1; /用来辅助跳出嵌套外循环 /shift函数外围开始 if(strcmp(sub1,t)!=0) /shift函数范围开始 if(tn-1!=si-1)/坏字符算法 for(k=0;kn&flag;k+)/在子串中找坏字符 if(tk=si-1)/找到,跳出循环for shift=n-k-1; flag=0; break; if(k=n-1&tk!=si-1) shift=n; flag=0; break; / printf(n坏字符时移动的距离为%dn,shift); else shift=1;/匹配成功，后移一位； /shift外围函数 /for函数结束 return 0;6. 效率分析： 此算法时间复杂度明显要优于穷举算法，因为穷举算法要挨个移动比较字符串，而该算法可能一次移动多个距离，继而会缩短时间，提高效率。 而且当子字符串T越长，所含元素差异越大，效率就会越高,因为此时T串内更容易遇到好字符，而且T越长移动距离约长。三 . cloudy算法： 1. 算法起源： 提出者和时间不确定2. 算法基本思想： 算法先比较T串和对应S提取串中后面元素，先比较最后一个元素，如果串不等时最后元素不等或者字符串匹配（此时输出i），则后移一位继续比较，若最后一个元素相等则开始好后缀算法核心思路：在比较倒数第二个元素是否相等，依次往前，假设最后相等长度为m, 则在T串内从前向后查找是否有和后m位相等的短串，若未找到，则在T内从前向后找有无和后m-1长度的字符串，找到后以此为与T后面对应元素字符距离差为移动距离，继而得到好后缀算法。 3. 案例分析： 假设母串S : edgoodbnbqgoodadecmnkdewuopimmxccaluhfui若子串为T1 : cnkdmnk 假设已经比较到第15位 edgoodbnbqgoodadecmnkdewuopimmxccaluhfuicnkdmnkcnkdmnk在第15位时母串待匹字符串adecmnk ,而子串cnkdmnk ,后三位相同, 为mnk 此时从T串寻找，发现没有mnk 然后寻找发现前面有nk,而此nk和T内后nk相差 4位，故而得到应该后移4位，然互继续比较，如此循环直到结束。4. 算法具体实现： 字符串的物理存储实现 malloc函数申请空间返回unsigned char 型指针，线性结构 ； 设置参数 : i, 用以表示检测位，范围为（lengthT，lengthS）用for循环语句判断是否走完S字符串。辅助函数 ：Substring（S , i，n）作用为提取S字符串里从第i 位起长度为 n 的字符串 ，其返回值为unsigned char型指针。同穷举算法；5. 算法源码：status cloudy(string s,string t) int m,n;/母子串长度+1 m=strlen(s); n=strlen(t); int i=n;/检索总长变量n-m int b,bz;/坏字符在母子串位子 int shift=0;/应该移动长度 int suf ;/好字符长度 unsigned char* sub1; sub1=malloc(10000*sizeof(unsigned char); 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,sub1i);/输出sub11字符串 printf(n); */ /shift函数外围开始 if(strcmp(sub1,t)!=0) /shift函数范围开始 if(tn-1!=si-1)/坏字符算法 shift=1; else /好后缀 int a=0,g=1;/g为好后缀个数 for(a;an;a+) if(tn-a-2=si-a-2) +g; else break; / printf(n输出好后缀字符个数%d,g); / 寻找好前缀： / 用来求得shiftg int h; int shift=-1;/初始值，用来判断后面 string test; string good; test=malloc(10000*sizeof(unsigned char); good=malloc(10000*sizeof(unsigned char); lop: for(h=1;h=n-g+1;h+) strcpy(good,substring(t,n-g+1,g) ); strcpy(test,substring(t,h,g) ); if(strcmp(good,test)=0) shift=n-g+1-h; break; if(shift1) -g; goto lop; if(shift=0) /printf(n输出n%dn,n); shift=n; / printf(n好后缀时需要移动的距离是%d,shift); /shift函数范围 /shift外围函数 /while函数结束 return 0;6. 效率分析：此算法综合效率远远高于暴力穷举算法，因为该算法不必挨个比较S串内容，可以一次移动多个距离。 与sundy算法相比，这种算法解决的方式不同，二者一个好后缀一个坏字符，当T串元素多样性较高且较长时，二者效率都非常高， 但是当S相邻字符短组合与T串有重叠时，该算法效率高于sundy，而当非常随机，元素毫无规律时sundy算法效率更好。四 . BM（Boyer-Moore）算法： 1. 起源：1977年，Robert S.Boyer和J Strother Moore提出了另一种在O(n)时间复杂度内，完成字符串匹配的算法，其在绝大多数场合的性能表现，2. 算法基本思想：此算法是一种综合sundy算法和好后缀算法的组合算法，充分利用了二者的优点，进一步提高了效率。 其基本思路在于从S中提取待匹字符串，若匹配成功则后移一位，若不成功，同样从最后一个元素开始比较，满足坏字符则用坏字符算法，若满足好字符算法，则需要两方面，一方面运用好字符算法求得需要移动距离shift1,另外从后往前第一个不相等元素处利用坏字符算法，算出移动距离shift2，比较shift1 和 shift2 大小，大的即为移动的距离。判断走完S算法结束。3. 案例分析：有了第二第三种算法的分析，此算法思路已经比较显而易见，只需注意分情况运用两种算法，而且好后缀时需要比较大小确定移动距离，就可以解决问题。4. 算法具体实现： 字符串的物理存储实现 malloc函数申请空间返回unsigned char 型指针，线性结构 ； 设置参数 : i, 用以表示检测位，范围为（lengthT，lengthS）用for循环语句判断是否走完S字符串。辅助函数 ：Substring（S , i，n）作用为提取S字符串里从第i 位起长度为 n 的字符串 ，其返回值为unsigned char型指针。同穷举算法；5. 算法源码：status bm(string s,string t) int m,n;/母子串长度+1 m=strlen(s); n=strlen(t); int i=n;/检索总长变量n-m int b,bz;/坏字符在母子串位子 int shift=0;/应该移动长度 int suf ;/好字符长度 int k;/计数 unsigned char* sub1; sub1=malloc(10000*sizeof(unsigned char); printf(nBM算法运行得：); for(;i=m; i=i+shift)/判断母串是否检测完 int flag=1;/用来辅助跳出嵌套外循环 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,sub1i);/输出sub11字符串 printf(n); */ /shift函数外围开始 if(strcmp(sub1,t)!=0) /shift函数范围开始 if(tn-1!=si-1)/坏字符算法 for(k=0;kn&flag;k+)/在子串中找坏字符 if(tk=si-1)/找到,跳出循环for shift=n-k-1; flag=0; / break; if(k=n-1&tk!=si-1) shift=n; flag=0; break; / printf(坏字符时移动的距离为%dn,shift); else /好后缀 int a=0,g=1;/g为好后缀个数 for(a;an;a+) if(tn-a-2=si-a-2) +g; else break; / printf(n输出好后缀字符个数%d,g); / 寻找好前缀： / 用来求得shiftg int h; int shift=-1;/初始值，用来判断后面 string test; string good; test=malloc(10000*sizeof(unsigned char); good=malloc(10000*sizeof(unsigned char); lop: for(h=1;h=n-g+1;h+) strcpy(good,substring(t,n-g+1,g) ); strcpy(test,substring(t,h,g) ); if(strcmp(good,test)=0) shift=n-g+1-h; break; if(shift1) -g; goto lop; if(shift=0) /printf(n输出n%dn,n); shift=n; / printf(n好后缀时需要移动的距离是%d,shift); /shift函数范围 /shift外围函数 /while函数结束return 0;6. 效率分析： 此算法综合了好后缀和坏字符算法，对于各种情况都有非常好的效率。效率优于穷举算法也优于好后缀坏字符算法，无论是面对毫无相关的元素组合，还是有逻辑组合关系的字符串都能很好的匹配，而且T串长度越长往往效率会越高。O(n)时间复杂度（三），总程序源代码。源代码：#include #include #include #define error 0#define CHAR_MAX 30typedef int status;typedef unsigned char *string;status substring( string s,int pose ,int len );void index(string s, string t);int main() int i=0,a,wo; char ch; string s,t,m; string sub; s=malloc(10000*sizeof(unsigned char); t=malloc(10000*sizeof(unsigned char); m=malloc(10000*sizeof(unsigned char); printf(n); printf(n); printf(- n); printf(几种字符串匹配算法实测：n); printf(n); printf( 按 1 手动输入母字符串S n); printf( 按 2 以TXT格式文章作为母字符串S n); printf( 按 其他键 退出该程序 n); scanf(%d,&wo); printf(n); printf(- n); switch(wo) case 1: printf(请输入母字符串S内容: n); ch = getchar(); while(ch = getchar() !=n) si=ch; i+; si=0; ; break ; case 2: printf(n); printf(n); printf(母字符串S内容为: n); char chf; FILE* fp; fp = fopen(c:example3.txt,r); /只供读取 if(fp = NULL) /如果失败了 printf(ERROR！); return 1; int kl=0; /getc()用于在打开文件中获取一个字符 while(chf = getc(fp) != EOF) /循环获取直至文件结束 EOF标志(End Of File) skl=chf; /打印获取到的字符 kl+; skl=0; fclose(fp); /关闭文件 printf(n); int as=0; for(;askl;as+) printf(%c,sas); printf(n); ; break; default : return 0; break; / printf(字符串长度是：%d,strlen(s);/strlen(s)返回值为字符串长 /printf(n 输出s内容:n); / for(i=0;istrlen(s);i+) / printf(%c,si); printf(n); printf(-n); printf(n); printf(请输入子字符串T内容 : n); printf(n); i=0; ch=getchar(); while(ch = getchar() !=n) ti=ch; i+; ti=0; printf(-n); /* printf(字符串长度是：%d,strlen(t);/strlen(s)返回值为字符串长 printf(n输出t内容:n); for(i=0;istrlen(t);i+) printf(%c,ti);*/ /* strcpy(t,mnkec);/字符串之间赋值函数； printf(nt字符串长度是%dn,strlen(t); printf(n输出t字符串：n); for(i=0;istrlen(t);i+) printf(%c,ti); */ /* strcpy( m,strcat(s,t); / 编译器自带字符串连接函数stracat printf(n输出m字符串：n); for(i=0;istrlen(m);i+) printf(%c,mi); strcpy(sub,substring(s,3,2); /substring函数的验证； printf(n输出sub字符串：n); for(i=0;istrlen(sub);i+) printf(%c,subi); printf(n字符串长：%dn,strlen(sub);*/ printf(n); bm(s,t); sundy(s,t); cloudy(s,t); index(s,t); return 0;/上为主函数；status substring( string s,int pose ,int len )/ 子字符串提取函数substring；返回值为子str字符串 unsigned char* sub; sub=malloc(10000*sizeof(unsigned char); int i=strlen(s); int k=pose+len-1; if(ii|ki) return NULL; int a; for( a=0;alen;a+,pose+) suba=spose-1; suba=0; return sub;status bm(string s,string t) int m,n;/母子串长度+1 m=strlen(s); n=strlen(t); int i=n;/检索总长变量n-m int b,bz;/坏字符在母子串位子 int shift=0;/应该移动长度 int suf ;/好字符长度 int k;/计数 unsigned char* sub1; sub1=malloc(10000*sizeof(unsigned char); printf(nBM算法运行得：); for(;i=m; i=i+shift)/判断母串是否检测完 int flag=1;/用来辅助跳出嵌套外循环 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,sub1i);/输出sub11字符串 printf(n); */ /shift函数外围开始 if(strcmp(sub1,t)!=0) /shift函数范围开始 if(tn-1!=si-1)/坏字符算法 for(k=0;kn&flag;k+)/在子串中找坏字符 if(tk=si-1)/找到,跳出循环for shift=n-k-1; flag=0; / break; if(k=n-1&tk!=si-1) shift=n; flag=0; break; / printf(坏字符时移动的距离为%dn,shift); else /好后缀