24数据结构笔记之二十四串的模式匹配算法

24、蛤蟆的数据结构笔记之二十四串的模式匹配算法本篇名言：“燧石受到的敲打越厉害，发出的光就越灿烂。--马克思”来看下两个算法，BF和KMP算法在串的模式匹配中实现。1.BF算法BF(BruteForce)算法是普通的模式匹配算法，BF算法的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配，若相等，则继续比较S的第二个字符和T的第二个字符；若不相等，则比较S的第二个字符和T的第一个字符，依次比较下去，直到得出最后的匹配结果。BF算法是一种蛮力算法。首先S[1]和T[1]比较，若相等，则再比较S[2]和T[2]，一直到T[M]为止；若S[1]和T[1]不等，则T向右移动一个字符的位置，再依次进行比较。如果存在k，1≤k≤N，且S[k+1…k+M]=T[1…M]，则匹配成功；否则失败。该算法最坏情况下要进行M*(N-M+1)次比较，时间复杂度为O(M*N)。如下图1：2.KMP算法KMP算法是一种改进的字符串匹配算法，由D.E.Knuth与V.R.Pratt和J.H.Morris同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称KMP算法）。KMP算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next()函数，函数本身包含了模式串的局部匹配信息。主串：abacaabacabacabaabb，下文中我们称作T模式串：abacab，下文中我们称作W在暴力字符串匹配过程中，我们会从T[0]跟W[0]匹配，如果相等则匹配下一个字符，直到出现不相等的情况，此时我们会简单的丢弃前面的匹配信息，然后从T[1]跟W[0]匹配，循环进行，直到主串结束，或者出现匹配的情况。这种简单的丢弃前面的匹配信息，造成了极大的浪费和低下的匹配效率。然而，在KMP算法中，对于每一个模式串我们会事先计算出模式串的内部匹配信息，在匹配失败时最大的移动模式串，以减少匹配次数。比如，在简单的一次匹配失败后，我们会想将模式串尽量的右移和主串进行匹配。右移的距离在KMP算法中是如此计算的：在已经匹配的模式串子串中，找出最长的相同的前缀和后缀，然后移动使它们重叠。在第一次匹配过程中T:abacaabacabacabaabbM:abacab在T[5]与W[5]出现了不匹配，而T[0]~T[4]是匹配的，现在T[0]~T[4]就是上文中说的已经匹配的模式串子串，现在移动找出最长的相同的前缀和后缀并使他们重叠：T:abacaabacabacabaabbM:abacab然后在从上次匹配失败的地方进行匹配，这样就减少了匹配次数，增加了效率。如下图23.算法实现BF实现BF实现，通过第一个字母开始，一个字母一个字母的回溯实现。最后返回第几个字母开始匹配成功。intBFMatch(char*s,char*p){inti,j;i=0;while(istrlen(s)){j=0;while(s[i]==p[j]&&jstrlen(p)){i++;j++;}if(j==strlen(p))returni-strlen(p);i=i-j+1;//指针i回溯}return-1;}KMP实现KMP算法多了一个getNext函数，该函数是将模式匹配项进行处理得到一个数组。数组中是一组整型数字，个数和匹配字符串一样多。每个整型表示，如果NEXT值为{-1,0,0,0，1,2,3,4,5}，如果,模式匹配和字符串在第7个字母匹配出错（第7个数组值是3），那么模式匹配串重新往右移动3个字母然后重新和字符串进行匹配，如果又匹配失败，那么第3个数组是0，那么匹配字符串重新和字符串进行到的下一个字母进行匹配。//getNetxvoidgetNext(char*p,int*next){intj,k;next[0]=-1;j=0;k=-1;while(jstrlen(p)-1){if(k==-1||p[j]==p[k])//匹配的情况下,p[j]==p[k]{j++;k++;next[j]=k;}else{//p[j]!=p[k]k=next[k];}}}//KMPintKMPMatch(char*s,char*p){intnext[100];inti,j;i=0;j=0;getNext(p,next);while(istrlen(s)){if(j==-1||s[i]==p[j]){i++;j++;}else{j=next[j];//消除了指针i的回溯}if(j==strlen(p)){returni-strlen(p);}}return-1;}4.BF和KMP算法源码最后如下图3所示：#define_CRT_SECURE_NO_WARNINGS#includestdio.h#includestdlib.h#includestring.h#defineMAX_SIZE255//定义字符串的最大长度typedefunsignedcharSString[MAX_SIZE];//数组第一个保存长度//BFintBFMatch(char*s,char*p){inti,j;i=0;while(istrlen(s)){j=0;while(s[i]==p[j]&&jstrlen(p)){i++;j++;}if(j==strlen(p))returni-strlen(p);i=i-j+1;//指针i回溯}return-1;}//getNetxvoidgetNext(char*p,int*next){intj,k;next[0]=-1;j=0;k=-1;while(jstrlen(p)-1){if(k==-1||p[j]==p[k])//匹配的情况下,p[j]==p[k]{j++;k++;next[j]=k;}else{//p[j]!=p[k]k=next[k];}}}//KMPintKMPMatch(char*s,char*p){intnext[100];inti,j;i=0;j=0;getNext(p,next);while(istrlen(s)){if(j==-1||s[i]==p[j]){i++;j++;}else{j=next[j];//消除了指针i的回溯}if(j==strlen(p)){returni-strlen(p);}}return-1;}intmain(){inta,b;chars[MAX_SIZE],p[MAX_SIZE];printf(请输入模式串：);scanf(%s,&s);printf(请输入子串：);scanf(%s,&p);a=BFMatch(s,p);b=KMPMatch(s,p);if(a!=-1){printf(使用BF算法：%d\n,a);}else{printf(未匹配\n);}if(b!=-1){printf(使用KMP算法：%d\n,a);}else{printf(未匹配\n);}system(pause);}