本文共 7665 字，大约阅读时间需要 25 分钟。

串的模式匹配算法(KMP算法，BF算法+算法详解+实现代码)

子串的定位操作是找子串在主串中从第pos个字符后首次出现的位置，又被称为串的模式匹配

一、BF模式匹配算法

• BF算法思想:Brute-Force算法又称蛮力匹配算法(简称BF算法),从主串S的第pos个字符开始，和模式串T的第一个字符进行比较，若相等，则继续比较后续字符；否则回溯到主串S的第pos+1个字符开始重新和模式串T进行比较。以此类推，直至模式串T中的每一个字符依次和主串S中的一个连续的字符序列相等，则称模式匹配成功，此时返回模式串T的第一个字符在主串S中的位置；否则主串中没有和模式串相等的字符序列，称模式匹配不成功。

• BF算法思想:

  从主串S的第pos个字符开始的子串与模式串T比较的策略是从前到后依次进行比较。因此在主串中设置指示器i表示主串S中当前比较的字符；在模式串T中设置指示器j表示模式串T中当前比较的字符。

• 实例分析:

  给定主串为S=“ababcabcacbab”,T=“abcac”。匹配过程如下
  

• 实现代码:

//BF模式匹配算法int Index(HString S, int pos, HString T) {
   	int i = pos;//主串从pos开始	int j = 1;//模式串从头开始	while (i <= S.len&&j <= T.len) {
   		if (S.ch[i] == T.ch[j]) {
   //当对应字符相等时，比较后续字符			i++;			j++;		}		else {
   //当对应字符不相等时			i = i - j + 2;//主串回溯到i-j+2的位置重新比较			j = 1;//模式串从头开始重新比较		}	}	if (j > T.len) {
   //匹配成功时，返回匹配起始位置		return i - T.len;	}	else {
   //匹配失败，返回0		return 0;	}}

• 算法分析:
• • BF算法的思想比较简单，但当在最坏情况下，算法的时间复杂度为O(n*m),其中n和m分别是主串和模式串的长度。这个算法的主要事件耗费在失配后的比较位置有回溯，因而比较次数过多。为降低时间复杂度可采用无回溯的算法。

二、KMP模式匹配算法(重点)

• KMP算法思想
  Knuth-Morris-Pratt算法（简称KMP），是由D.E.Knuth、J.H.Morris和V.R.Pratt共同提出的一个改进算法。KMP算法是模式匹配中的经典算法，和BF算法相比，KMP算法的不同点是消除BF算法中主串S指针回溯的情况，从而完成串的模式匹配，这样的结果使得算法的时间复杂度仅为O(n+m)。
• KMP算法描述
  KMP算法每当一趟匹配过程中出现字符比较不相等时，主串S的i指针不需要回溯，而是利用已经得到的“部分匹配”结果将模式串向右滑动一段距离后，继续进行比较 。
• next函数
  在实现算法之前，我们需要引入next函数：若令next[j]=k,则next[j]表明当模式中第j个字符与主串中相应字符“失配”时，在模式中需重新和主串中该字符进行比较的当前字符的位置。由此引出next函数的定义：
  
  由此可见，next函数的计算仅与模式串本身有关，和主串无关。其中’T1T2…T(k-1)'时’T1T2…T(j-1)'的真前缀子串，
  ‘T(j-k+1)T(j-k+2)…T(j-1)’是’T1T2…T(j-1)'的真后缀子串。当next函数定义中的集合不为空时，next[j]的值等于串’T1T2…T(j-1)'的真前缀子串和真后缀子串相等时的最大子串长度+1
  通过以上分析，推导出模式串"abaabcac"的next值的计算过程如下表所示.
  (1).当j=1时，由定义得知，next[1]=0;
  (2)当j=2时，满足1<k<j的k值不存在，由定义得知next[2]=1;
  
  则我们可以得出next值
  
• 匹配过程如下：
  在求得模式串的next函数之后，匹配可按如下进行：假设指针i和j分别指示主串S和模式串T中当前比较的字符，令i的初始值为pos,j的初值为1。若在匹配过程中Si=Tj,则i和j分别增1；否则，i不变，而j退到next[j]位置再比较(即Si和Tnext[j]进行比较)，若相等，则指针各自增1，否则j再退到下一个next值得位置，以此类推，直至下列两种可能:
  第一种:j退到某个next值(next[…next[j]])时字符比较相等，则指针各自增1继续进行匹配；
  第二种是j退到next值为0(即与模式串得第一个字符失配)，则此时需将主串和模式串同时向右滑动一个位置(此时j=0,当向右滑动一个位置时，即模式串得第一个字符)，即从主串得下一个字符Si+1和模式串T1重新开始比较。
  
• 求next[]的算法如下：

void Get_Next(HString T, int next[]) {
   	int j = 1, k = 0;	next[1] = 0;	while (j < T.len) {
   		if (k == 0 || T.ch[j] == T.ch[k]) {
   			++j;			++k;			next[j] = k;		}		else {
   			k = next[k];		}	}}

三、改进的KMP算法

我们在前面介绍的next函数虽然好用，但还不够完美，在某种情况下是有缺陷的，例如如下匹配过程

主串为"aaabaaaab" 模式串为"aaaab"

在求得模式串的next值之后，匹配过程如下:

从串的匹配过程可以看到，当i=4，j=4时，S4!=T4,由next[j]所示还需进行i=4、j=3,i=4、j=2,i=4、j=1这三次比较。实际上，因为模式串中的第1、2、3个字符和第4个字符都相等(即都是’a’)，因此，不需要再和主串中第4个字符相比较，而可以直接将模式串一次向右滑动4个字符的位置直接进行i=5、j=1的判断。 这就是说，若按上述定义得到next[j]=k,而模式串中T(j)!=T(k),则当Si != Tj时，不需要进行Si和Tk的比较，直接和Tnext[k]进行比较；换句话说，此时的next[j]的值应和next[k]相同，为此将next[j]修正为nextval[j]。而模式串中Tj !=Tk,则当Si !=Tj时，还是需要比较Si和Tk的比较，因此nextval[j]的值就是k,即nextval[j]得值就是next[j]的值。 通过以上分析，计算第j个字符得nextval值时，要看第j个字符是否和第j个字符的next值指向的字符相等。若相等，则nextval[j]=nextval[next[j]]；否则，nextval[j]=next[j]。 由此推导出模式串T='aaaab’的nextval值的计算过程如下:

• 当j=1时，由定义知，nextval[1]=0;
• 当j=2时，由next[2]=1,且T2=T1,则nextval[2]=nextval[1],即nextval[2]=0;
• 当j=3时，由next[3]=2,且T3=T2,则nextval[3]=nextval[2],即nextval[3]=0;
• 当j=4时，由next[4]=3,且T4=T3,则nextval[4]=nextval[3],即nextval[4]=0；
• 当j=5时，由next[5]=4,且T5不等于T4,则nextval[5]=next[5],即nextval[5]=4.
  则模式串"aaaab"的nextval函数值如下所示。
  
• 改进后的匹配过程如下：
  
  可以看到匹配次数大大减少，降低了复杂度。
• nextval函数实现代码如下
  nextval[]时基于next[]函数实现的。

void Get_Next(HString T, int next[]) {
   	int j = 1, k = 0;	next[1] = 0;	while (j < T.len) {
   		if (k == 0 || T.ch[j] == T.ch[k]) {
   			++j;			++k;			next[j] = k;		}		else {
   			k = next[k];		}	}}void Get_NextVal(HString T, int next[], int nextval[]) {
   	int j = 2, k = 0;	Get_Next(T, next);	nextval[1] = 0;	while (j <= T.len) {
   		k = next[j];		if (T.ch[j] == T.ch[k]) {
   			nextval[j] = nextval[k];		}		else {
   			nextval[j] = next[j];		}		j++;	}}

通常，模式串的长度m比主串的长度n小很多，且计算next或者nextval函数的时间复杂度为O(m)。因此，对于整个匹配算法来说，所增加的计算next或nextval时值得的。

BF算法的时间复杂度为O(m*n),但是实际接近于O(n+m),因此至今仍被采用。KMP算法仅当模式串与主串之间存在许多“部分匹配”的情况下，才会比BF算法快。KMP算法的最大特点就是主串的指针不需要回溯，整个匹配过程中，主串仅需从头到尾扫描一次，对于处理从外设输入的庞大文件很有效，可以边读边匹配。

四、KMP以及BF的完整代码实现。(Visual Studio 2017开发环境)

头文件:DString.h

#pragma once#include
   
    typedef struct {
   //堆串存储结构	char *ch;//若是非空串，则是指向串的起始地址；否则为空	int len;//字符串的长度}HString;//串初始化函数void HStrInit(HString *S) {
   	S->ch = NULL;	S->len = 0;}//串赋值函数int HStrAssign(HString *S, const char *chars) {
   	int i = 0;	if (NULL == chars || NULL == S) {
   		return 0;	}	else {
   		while (chars[i] != '\0') {
   			i++;		}		S->len = i;//串S的长度等于串chars的长度		if (0 != S->len) {
   			if (S->ch != NULL) {
   				free(S->ch);			}			S->ch = (char *)malloc(sizeof(char)*(S->len + 1));//0号单元不用，故比实际需求多开辟一个空间			if (NULL == S->ch) {
   //空间开辟失败				return 0;			}			for (i = 1; i <= S->len; i++) {
   //将chars的内容逐一赋值给S->ch				S->ch[i] = chars[i - 1];			}		}		else {
   			S->ch = NULL;//当chars的长度为0时，则置S为空串。		}		return 1;	}}//打印void print(HString *S) {
   	for (int i = 1; i <= S->len; i++) {
   		printf("%c", S->ch[i]);	}	printf("\n");}//BF模式匹配算法int Index(HString S, int pos, HString T) {
   	int i = pos;//主串从pos开始	int j = 1;//模式串从头开始	while (i <= S.len&&j <= T.len) {
   		if (S.ch[i] == T.ch[j]) {
   //当对应字符相等时，比较后续字符			i++;			j++;		}		else {
   //当对应字符不相等时			i = i - j + 2;//主串回溯到i-j+2的位置重新比较			j = 1;//模式串从头开始重新比较		}	}	if (j > T.len) {
   //匹配成功时，返回匹配起始位置		return i - T.len;	}	else {
   //匹配失败，返回0		return 0;	}}//统计BF模式匹配算法的比较次数int IndexCount(HString S, int pos, HString T) {
   	int i = pos;//主串从pos开始	int j = 1;//模式串从头开始	int count = 0;	while (i <= S.len&&j <= T.len) {
   		if (S.ch[i] == T.ch[j]) {
   //当对应字符相等时，比较后续字符			i++;			j++;		}		else {
   //当对应字符不相等时			i = i - j + 2;//主串回溯到i-j+2的位置重新比较			j = 1;//模式串从头开始重新比较		}		count++;	}	return count;	}//KMP模式匹配算法void Get_Next(HString T, int next[]) {
   	int j = 1, k = 0;	next[1] = 0;	while (j < T.len) {
   		if (k == 0 || T.ch[j] == T.ch[k]) {
   			++j;			++k;			next[j] = k;		}		else {
   			k = next[k];		}	}}void Get_NextVal(HString T, int next[], int nextval[]) {
   	int j = 2, k = 0;	Get_Next(T, next);	nextval[1] = 0;	while (j <= T.len) {
   		k = next[j];		if (T.ch[j] == T.ch[k]) {
   			nextval[j] = nextval[k];		}		else {
   			nextval[j] = next[j];		}		j++;	}}int Index_KMP(HString S, int pos, HString T,int nextval[]) {
   	int i = pos;//主串从第pos开始	int j = 1;//模式串从头开始	while (i <= S.len&&j <= T.len) {
   		if (j == 0 || S.ch[i] == T.ch[j]) {
   //继续比较后继字符			++i;			++j;		}		else {
   			j = nextval[j];		}	}	if (j > T.len) {
   //匹配成功		return i - T.len;//返回匹配的起始位置	}	else {
   		return 0;	}}//统计KMP算法的比较次数int Index_KMPCount(HString S, int pos, HString T, int nextval[]) {
   	int i = pos;//主串从第pos开始	int j = 1;//模式串从头开始	int count = 0;	while (i <= S.len&&j <= T.len) {
   		if (j == 0 || S.ch[i] == T.ch[j]) {
   //继续比较后继字符			++i;			++j;		}		else {
   			j = nextval[j];		}		count++;	}	return count;}
   

源文件:

#include
   
    #include
    
     #include
     
      #include"DString.h"int main() {
   	HString S;	HString T;	HStrInit(&S);	HStrInit(&T);	char a[] = "aaabaaaab";	char b[] = "aaaab";	HStrAssign(&S, a);	HStrAssign(&T, b);	printf("主串:");	print(&S);	printf("模式串:");	print(&T);	printf("BF模式匹配:\n");	int index = Index(S, 1, T);	int count1 = IndexCount(S, 1, T);	printf("index=%d\n", index);	printf("比较次数:%d\n", count1);	printf("KMP模式匹配:\n");	int *next,*nextval;	next = (int *)malloc(sizeof(int)*(T.len + 1));	nextval = (int *)malloc(sizeof(int)*(T.len + 1));	Get_NextVal(T,next,nextval);	printf("next[]数组如下\n");	for (int i = 1; i < (T.len + 1); i++) {
   		printf("%d ", next[i]);	}	printf("\nnextval[]数组如下:\n");	for (int i = 1; i < (T.len + 1); i++) {
   		printf("%d ", nextval[i]);	}	printf("\n");	int index1 = Index_KMP(S, 1, T, next);	int count2 = Index_KMPCount(S, 1, T, nextval);	printf("index1=%d\n", index1);	printf("比较次数:%d\n",count2);	system("pause");	return 0;}
     
    
   

五、测试结果如下

转载地址：http://fnzzi.baihongyu.com/