KMP算法

KMP算法是一个字符串算法，通常用于匹配字符串。

KMP算法的原理

如果我们暴力枚举下标 \(i,j\)，\(i\) 是文本串的下标，\(j\) 是模式串（你要在文本串中匹配的字符串）的下标，时间复杂度 \(O(NM)\)，其中 \(N,M\) 分别为文本串和模式串的长度。

我们看一下匹配过程：（gif 动图请耐心观看）

时间复杂度高吧，出题人随便就 \(hack\) 掉了。

咦？我们会发现 \(文本串.substr(3,4)=模式串.substr(1,4)=模式串.substr(3,4)="xyxy"\)，这样我们 \(i=7,j=7\) 匹配失败时可以跳 \(2\) 次（\(j=3\)），就可以达到正确性和时间复杂度平衡的效果。

我们维护 \(nxt_i\) 表示s和s以i结尾的最长公共前后缀的长度，这样我们在 \(文本串_i,模式串_j\) 匹配失败时 \(j\) 可以直接跳到 \(nxt_j\)。

维护 nxt_i

若 \(s_i==s_j\) 也就是 \(模式串_i,模式串_j\) 匹配时，nxt[++i]=++j（其他同理写法也可以，最好固定一个写法），否则按文本串和模式串匹配失败来。

代码

void getNext(string s)//初始化和文本串没关系
{
	nxt[0] = -1;
	int i = 0, j = -1;
	while (i < s.size())
		if (j == -1 || s[i] == s[j])
			nxt[++i] = ++j;
		else
			j = nxt[j];
	return;
}
void KMP(string s, string t)//P3375的询问代码
{
	getNext(t);
	int i = 0, j = 0;
	while (i < s.size())
	{
		if (j == t.size() - 1 && s[i] == t[j])
		{
			cout << i - j + 1 << '\n';
			j = nxt[j];
		}
		if (j == -1 || s[i] == t[j])
			i++, j++;
		else
			j = nxt[j];
	}
	return;
}

KMP算法应用

P3375 【模板】KMP

P4391 [BOI2009] Radio Transmission 无线传输

给你一个字符串 \(s_1\)，它是由某个字符串 \(s_2\) 不断自我连接形成的（保证至少重复 \(2\) 次）。但是字符串 \(s_2\) 是不确定的，现在只想知道它的最短长度是多少。

不想说过程，直接说结论：ans = n - nxt[n]

CF1200E Compress Words

cin >> n;
for (int i = 1; i <= n; i++)
{
	cin >> s;
	if (ans.empty())
		ans = s;
	else
	{
		int len = min(s.size(), ans.size());
		string s1 = s.substr(0, len);
		string s2 = ans.substr(ans.size() - len, len);
		string s3 = s1 + "#" + s2;//中间必须拼上"#"，不然有可能最长公共前后缀重合。
		getNext(s3);
		ans += s.substr(nxt[s3.size()]);
	}
}
cout << ans;