KMP字符串

KMP字符串

来源：2025年校外实训一Week1(李胜睿班) B19

---

题目分析：看起来人畜无害的字符串模式匹配，但是数据规模大的吓人。暴力模式匹配算法的时间复杂度为O(nm)，其中n和m分别是模式串和主串的长度，本题n和m的规模分别是1e5和1e6，显然，暴力模式匹配算法是会TLE的，我们需要使用KMP算法来解决这个问题。

---

算法分析：让我们来了解一下KMP算法，这是一个专门用于字符串模式匹配的算法，可以在O(n+m)的时间复杂度内匹配出主串中所有模式子串的位置

首先让我们了解几个概念

• 字符串的前缀：以字符串第一个字符开始的所有字符串的子串（除去其本身）
• 字符串的后缀：以字符串最后一个字符结束的所有字符串的子串（除去其本身）
• 最大相同前后缀长度：顾名思义，一个字符串相同的前缀和后缀中，长度最大的那一对前后缀的长度，如果没有相同的前缀和后缀，那么最大前后缀长度为0
• 部分匹配表：一个int类型，容量与模式串长度相同的数组，不妨命名为nxt[i]。显然每个数组的元素对应字符串中的一个字符，其数值应等于模式串中以该字符结尾的前缀字符串的最大相同前后缀长度，原因稍后解释

现在假设我们要匹配这样的字符串：

模式串（pattern）：ABACABA

主串/待匹配串（match）：ABACABCBA

根据部分匹配表的定义，我们可以计算出nxt数组的值分别是[0, 0, 1, 0, 1, 2, 3]

让我们从头开始匹配，很快我们发现前四个字符匹配，第五个字符不匹配。这时，传统的暴力算法就直接回头，从主串的第二个元素再和模式串的第一个元素一个一个比过去了。如果模式串非常长，每次都是到最后一个字符发现不匹配，就会浪费大量的时间。我们已经比较过这么长的字符串了，难道就白比较了吗？这时我们发现，前四个已匹配的字符组成的字符串（下称为A串），其最大前后缀长度为1，这说明A串长度为1的前缀和长度为1的后缀完全相等，且没有更长的相同的前后缀，我们知道两个字符串完全匹配，则它们的前后缀也要完全匹配。我们匹配字符串的操作实际上是长度从小到大依次匹配两个字符串相同的前缀。而新开始匹配前缀的位置包含于A串的某个后缀之中。那么如果一个字符串有一个长度为x的的相同前后缀，则从这个后缀开始，把这个后缀作为新开始匹配的起点，接下来长度为x的前缀必然与模式串相同。而如果我们选择的是最长的相同前后缀，则表明该后缀之前的位置没有能匹配模式串的位置，那么不妨直接跳过这段，就从最长相同前后缀的后缀位置开始继续匹配，而接下来最大相同前后缀长度的一段必然是相同的，主串又回到了之前匹配的位置，而模板串从最大相同前后缀长度的位置开始匹配

具体的实现方法：我们使用变量i指向主串的某个位置，使用变量j指向模式串的位置

当pattern[j]!=match[i]时：

• 如果j!=0说明之前有一段已经匹配过的段落，我们便可以根据nxt数组查询这段已经匹配的字符串对应的最大相同前后缀长度，根据之前的分析，主串回到原位，模式串从最大相同前后缀长度的位置开始匹配，所以变量i保持不变，j=nxt[j-1]
• 如果j==0说明之前没有一段已经匹配过的段落，什么也不用做，只需让i增加1，继续从下一个位置从头开始匹配就好

当pattern[j]==match[i]时：说明该位置匹配，让i和j都增加1，继续匹配下一个位置

代码如下：

int j = 0;
vector<int> ans;
for (int i = 1; i < m; i++)
{
	while (j > 0 && pattern[j] != match[i])
	{
		j = nxt[j - 1];
	}//pattern[j]!=match[i]且j!=0时，持续将j根据nxt数组向前跳跃，显然nxt[i]的值必然小于等于i，且首位必定是0，所以j必然减小，不会出现无限循环的情况
	if (pattern[j] == match[i])
	{
		if (j == n - 1)
		{
			ans.push_back(i - n + 1);//完全匹配时，记录模式串出现的位置
			j = nxt[j];//完全匹配时匹配下一个，因为当前位置也匹配成功，所以使用nxt[j]即可
		}
		else
			j++;//未完全匹配时，j++，进入下一轮循环
	}
}

我们可以发现i一直单调递增，这就是KMP算法线性时间复杂度的关键。

不过我们还有一个问题，nxt数组该如何求出？这其实也是一个匹配模式串的问题，不过匹配的是自己的前后缀如果使用传统的暴力搜索方法，时间复杂度就是O(n^2)，而KMP算法时间复杂度O(n+m)。你想到了什么？没错，我们之前匹配主串不就是线性时间复杂度吗，有没有方法在求nxt数组时利用nxt数组来优化时间复杂度呢？有的兄弟有的！我们很容易发现求nxt[i+1]时需要匹配i+2长度的前后缀，而前i+1个长度都是已经在求nxt[i]时匹配过的，而这时nxt[i]已经被计算出来了，可以直接使用。这样我们就利用类似于动态规划的思想，线性扫描一遍模式串就求出了nxt数组。

代码如下，原理和匹配主串是类似的，不再过多阐释：

int j = 0;
for (int i = 1; i < n; i++) // j匹配前缀 i匹配后缀
{
	while (j > 0 && pattern[j] != pattern[i])
	{
		j = nxt[j - 1];
	}
	if (pattern[i] == pattern[j])
	{
		j++;
	}
	nxt[i] = j;
}

这样，先初始化nxt数组，时间复杂度为O(n)，再匹配主串，时间复杂度为O(m)，我们就得到了O(n+m)时间复杂度的模式串匹配算法，KMP算法

AC代码：

#include <iostream>
#include <vector>
using namespace std;
int n, m;
char pattern[100005];
int nxt[100005];
char match[1000005];
vector<int> ans;
int main()
{
	cin >> n >> pattern >> m >> match;
	int j = 0;
	for (int i = 1; i < n; i++) // j匹配前缀 i匹配后缀
	{
		while (j > 0 && pattern[j] != pattern[i])
		{
			j = nxt[j - 1];
		}
		if (pattern[i] == pattern[j])
		{
			j++;
		}
		nxt[i] = j;
	}
	j = 0;
	for (int i = 0; i < m; i++)
	{
		while (j > 0 && pattern[j] != match[i])
		{
			j = nxt[j - 1];
		}
		if (pattern[j] == match[i])
		{
			if (j == n - 1)
			{
				ans.push_back(i - n + 1);
				j = nxt[j];
			}
			else
				j++;
		}
	}
	for (int i : ans) cout << i << ' ';
	return 0;
}