算法案例分析—字符串模式匹配算法

hello！大家好哇，我是灰小猿，一个超会写bug的沙雕程序猿！

今天来和大家分享一个关于字符串比较的模式匹配算法，在数据结构中对字符串的相关操作中，对子串的定位操作通常称为串的模式匹配，同样他也是各种串处理中最重要的操作之一，同时子串也称为模式串，关于主串和模式串的匹配算法常用的主要有两种：朴素的模式匹配算法和KMP算法（改进的模式匹配算法），接下来将分别对这两种算法进行分析。

一、朴素的模式匹配算法

朴素的模式匹配算法也被称为布鲁特—福斯算法，其基本思想是：从主串的第一个字符起与模式串的第一个字符相比较，若相等，则逐一对之后的字符进行比较，否则从主串的第二个字符与模式串的第一个字符重新比较，直到模式串中的每一个字符依次与主串中连续的字符序列相匹配为止，这时就称为匹配成功，如果不能在主串中找到与模式串相匹配的内容，则称为匹配失败。

接下来举一个例子，以字符数组存储字符串，实现朴素的模式匹配算法。

//传入主串s和模式串t，同时设定从主串中开始匹配的位置pos
int index(char s[],char t[],int pos) {
	int i,j,slen,tlen;
	i = pos;
	j = 0;
	slen = s.length;	//获取到主串的长度
	tlen = t.length;	//获取到模式串的长度
	while (i<slen && j<tlen) {
		if (s[i] == t[j]) {
			i++;
			j++;
		}
		else {
			i = i-j+1;
			j=0;
		}		
	}
	if (j>=tlen) {
		return i-tlen;
	}
	return 1;
}

二、KMP算法（改进的模式匹配算法）

KMP算法是上一个算法的改进，相比于朴素的模式匹配算法，KMP算法在进行主串和模式串的匹配过程中，每当匹配过程中出现相比较的字符不相等时，不需要回退主串的字符位置指针，而是利用已经得到的“部分匹配”结果将模式串向右“滑动”尽可能远的距离，再继续进行比较。

设模式串为“P0...P(m-1)”,KMP匹配算法的思想是：当模式串中的字符Pj与主串中相应的字符Si不相等时，因其前j个字符（“P0...P(j-1)”）已经获得了成功的匹配，所以若模式串中的“P0...P(k-1)”与“P(j-k)...P(j-1)”相同，这时可令P0与Si相比较，从而使i无需回退。

在KMP算法中，依据模式串的next函数值可以实现子串的滑动，若令next[j]=k，则next[j]表示当模式串中的Pj与主串中相应的字符不相等时，令模式串的Pnext[j]与主串的相应字符进行比较，

关于next函数有如下的定义：

以下是求模式串的next函数的程序：

//求模式串p的next函数值，并存入数组next中
void Get_next(char *p,int next[])
{
	int i,j,slen;
	slen = strlen(p);	//获取到模式串的长度
	i=0;
	while (i<slen) {
		if (j==-1||p[i]==p[j]) {
			++i;
			++j;
			next[i] = j;
		} else {
			j = next[j];
		}
	}
}

在获取到的next函数后，

在KMP模式匹配算法中，设模式串的第一个字符下标为0，则KMP算法如下：

/*利用模式串p的next函数，求p在主串s中从第pos个字符开始的位置*/
/*若匹配成功，返回模式串在主串的位置下标，否则返回-1 */
int Index_KMP(char *s,char *p,int pos,int next[])
{
	int i,j,slen,plen;
	i=pos-1;
	j=-1;
	slen = strlen(s);	//求主串的长度
	plen = strlen(p);	//求模式串的长度
	while (i<slen && j<plen) {
		if (j==-1||s[i]==p[j]) {
			++i;
			++j;
		} else {
			j=next[j];
		}
	}
	if (j>=plen) {
		return i-plen;
	}
	else {
		return -1
	}
		
}

关于字符串模式匹配算法就分享到这里，有不足的地方还希望各位大佬一起指正，

觉得不错记得点赞关注哟！

大灰狼陪你一起进步！