KMP字符串匹配算法 | OI笔记

KMP字符串匹配

KMP是对字符串进行高效率匹配的方法

一些基本概念的解释：

• s 表示模式串(主串，一般是较长的一个)

• p 表示模板串(子串，一般是较短的一个)

• next数组表示 以 i 为终点的后缀和从 1 开始的前缀相等的情况中 后缀长度最长情况 的长度

暴力解法:

char s[N], p[M];
int ViolentMatch(char* s, char* p)
{
	int sLen = strlen(s);
	int pLen = strlen(p);
 
	int i = 0;
	int j = 0;
	while (i < sLen && j < pLen)
	{
		if (s[i] == p[j])
		{
			// 如果当前字符匹配成功（即S[i] == P[j]），则i++，j++
			i++;
			j++;
		}
		else
		{
			// 如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0
			i = i - j + 1;
			j = 0;
		}
	}
	//匹配成功，返回模式串p在文本串s中的位置，否则返回-1
	if (j == pLen)
		return i - j;
	else
		return -1;
}

不难发现，在子串 p 进行匹配的时候，每后移一段，都重复扫过了一些被重复匹配到的元素(绿色线条)，那么如何跳过这些元素呢？

如果将待匹配字符串 p 向后移动，移动的距离仅与他自己本身中重复的子段长度有关(如果没有重复子段，则移动长度为 sizeof(p))，那么用以下方法来表示：

p[1] ~ p[j] == p[i - j + 1] ~ p[i]

KMP核心： next[i] 数组的计算法则

代码模板：

const int N = 1e5, M = 1e6;
// N 为模板串长度，M 为模式串长度 
char p[N + 10], s[M + 10];
// p 为子串，s 为主串 
int ne[N + 10];
// 子串 p 的 next 数组 
int n, m;
// 子串长度 n 和主串长度 m  

cin >> n >> p + 1 >> m >> s + 1;
// 将子串和主串从 1 开始读入 

for (int i = 2, j = 0; i <= n; i ++)
{
	while (j && p[i] != p[j + 1]) j = ne[j];
	if (p[i] == p[j + 1]) j ++;
	ne[i] = j;
}
// 求子串的 next 数组 

for (int i = 1, j = 0; i <= m; i ++)
{
	while (j && s[i] != p[j + 1]) j = ne[j];
	if (s[i] == p[j + 1]) j ++;
	if (j == n)
	{
		printf("%d ", i - n);
		// 匹配成功，按题意执行操作 
		
		j = ne[j];
		// 继续进行的匹配操作 
	}
}
// 进行 KMP 匹配的过程

关于为什么求next数组和匹配的操作类似的问题

因为本质是一样的：
对于S串每一个特定的下标i，在满足 s[i-j+1，i] = p[0，j] 的前提下，我们需要找出 j 的最大值
唯一不同的在于，求 next 数组时，我们关心对于每个不同的下标 i 、j 能走多远；匹配时，我们只关心j是否走到末尾