KMP算法

KMP 算法主要由两部分组成

• 前缀函数
• 匹配

前缀函数(Prefix function) KMP的next函数

前缀函数是KMP思想的精髓

前缀函数的功能是求出模式串的next[]数组。那么，什么是模式串？什么是next数组？

举个栗子：

 “给出一个字符串T,再给出n个字符串S1、S2、…、Sn,问S1、S2,…,Sn中有哪些是T的子串？”

 在这个例子中，S1…是n个模式串，T是被匹配串。模式串是用来与被匹配穿匹配的。
 那么 next[]数组又是干什么的呢？这个next[]的概念就是前缀数组的精髓，KMP思想中精髓的精髓。

用一句话概括:

如果模式串P的前i个字符组成的子串为S，那么S的前next[i]个字符与S的后next[i]个字符相同

举例：

模式串P为ababaaab。next[5]的值为3。这说明P的前5个字符组成的字符串**ababa**的前3个字符与后3个字符相同，均为aba。

代码模板

/*
%% T是被踢配的串
%% P是模式串
%% 字符串都是下标1开始
*/
void Prefix(char *p){
	int m=strlen(p+1);
	next[1]=0;
	for(int k=0,q=2;q<=m;q++){
		while(k>0&&p[k+1]!=p[q])
			k=next[k];
		if(p[k+1]==p[q])
			k++;
		next[q]=k;
	}
}

KMP的匹配

 匹配部分主要依托next[]数组进行。其原理还是用一句话概括：

当被匹配穿的第i个字符T[i]与模式串的第j个字符不匹配时，将转而与模式串的第next[j-1]+1个字符匹配。

算法模板

void COMPUTE_PREFIX_FUNCTION(char P[])
{
	int m = strlen(P + 1);
	_next[1] = 0;
	for (int k = 0, q = 2; q <= m; q++)
	{
		while (k > 0 && P[k + 1] != P[q])
			k = _next[k];
		if (P[k + 1] == P[q])
			k++;
		_next[q] = k;
	}
}
int KMP_MATCHER(char T[], char P[])
{
	int n = strlen(T + 1), m = strlen(P + 1);
	COMPUTE_PREFIX_FUNCTION(P);
	int sum = 0;
	for (int i = 1, q = 0; i <= n; i++)
	{
		while (q > 0 && P[q + 1] != T[i])
			q = _next[q];
		if (P[q + 1] == T[i])
			q++;
		if (q == m)
		{
			sum++;
			q = _next[q];
		}
	}
	return sum;
}

使用模板