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

24、蛤蟆的数据结构笔记之二十四串的模式匹配算法本篇名言：“ 燧石受到的敲打越厉害，发出的光就越灿烂 -- 马克思 ”来看下两个算法，BF 和 KMP 算法在串的模式匹配中实现1.BF 算法BF(Brute Force)算法是普通的模式匹配算法，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()函数，函数本身包含了模式串的局部匹配信息主串：a b a c a a b a c a b a c a b a a b b，下文中我们称作 T模式串：a b a c a b，下文中我们称作 W在暴力字符串匹配过程中，我们会从 T[0] 跟 W[0] 匹配，如果相等则匹配下一个字符，直到出现不相等的情况，此时我们会简单的丢弃前面的匹配信息，然后从 T[1] 跟 W[0]匹配，循环进行，直到主串结束，或者出现匹配的情况这种简单的丢弃前面的匹配信息，造成了极大的浪费和低下的匹配效率然而，在 KMP 算法中，对于每一个模式串我们会事先计算出模式串的内部匹配信息，在匹配失败时最大的移动模式串，以减少匹配次数比如，在简单的一次匹配失败后，我们会想将模式串尽量的右移和主串进行匹配右移的距离在 KMP 算法中是如此计算的：在已经匹配的模式串子串中，找出最长的相同的前缀和后缀，然后移动使它们重叠在第一次匹配过程中T: a b a c a a b a c a b a c a b a a b bM: a b a c ab在 T[5]与 W[5]出现了不匹配，而 T[0]~T[4]是匹配的，现在 T[0]~T[4]就是上文中说的已经匹配的模式串子串，现在移动找出最长的相同的前缀和后缀并使他们重叠：T: a b a c aab a c a b a c a b a a b bM: a b a c ab然后在从上次匹配失败的地方进行匹配，这样就减少了匹配次数，增加了效率。

如下图 23.算法实现 BF 实现BF 实现，通过第一个字母开始，一个字母一个字母的回溯实现最后返回第几个字母开始匹配成功int BFMatch(char *s,char *p){int i,j;i=0;while(i #include#include#define MAX_SIZE 255 //定义字符串的最大长度typedef unsigned char SString[MAX_SIZE];//数组第一个保存长度//BFint BFMatch(char *s,char *p){int i,j;i=0;while(i < strlen(s)){j=0;while(s[i]==p[j]&&j < strlen(p)){i++;j++;}if(j==strlen(p))return i-strlen(p);i=i-j+1; //指针i回溯}return -1; }//getNetxvoid getNext(char *p,int *next){int j,k;next[0]=-1;j=0;k=-1;while(j < strlen(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];}}}//KMPint KMPMatch(char *s,char *p){int next[100];int i,j;i=0;j=0;getNext(p,next);while(i < strlen(s)){if(j==-1||s[i]==p[j]){i++;j++;}else{j=next[j]; //消除了指针i的回溯}if(j==strlen(p)){return i-strlen(p);}}return -1;}int main(){int a, b;char s[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");}。