KMP 学习笔记

这个人刚学会 KMP，你们快来嘲讽他。

先设出 $\pi_i$ 表示 $s_{1 \sim n}$ 的最长公共前后缀长度。

现在考虑已经知道了 $\pi_{1 \sim i-1}$，如何求出 $\pi_i$。

如果 $s_{\pi_{i-1}+1} = s_i$，那么本质上就是两个位置各向后推进一个，于是 $\pi_i = \pi_{i-1} + 1$。

那如果不是这样呢？

黑色是已经扫到的所有，红色是 $i-1$ 的答案，蓝色是新扩展的字符，黄色是答案。

可以看到，一开始新扩展的字符并不匹配。我们想要找到黄色。

聪明的你发现，两个黄框都在红框里面。要不然，就把两个红框合并吧？

你发现，黄框正好是红框的 $\pi$！若果还不是，还可以继续进行迭代。

于是，我们只要令初始值为 $\pi_{i-1}$，然后不断往回跳直到跳到 $0$ 或者匹配即可求出 $\pi_i$。

因此，求 $\pi$ 数组的代码其实极其简洁：

1
2
3
4
5
6


nxt[1]=0;
for(int i=2;i<=m;i++){
	while(p&&s2[i]!=s2[p+1])p=nxt[p];
	if(s2[i]==s2[p+1])p++;
	nxt[i]=p;
}

接下来转入正题：KMP。

令 $s$ 为主串，$t$ 为子串。

我们现在得知了整个字符串 $t$ 的 $\pi$。怎样匹配呢？

假如这一位匹配到 $s$ 成功了，我们就可以不理他；

否则，考虑这个情况：

除黑色外颜色相同的部分内容一样。可以看到在红和蓝的地方出现了失配。

此时，直接推倒重来就太亏了。

由于黄色的部分都是一样的，我们为什么不直接把前面的黄色部分拉到这里继续匹配呢？和上面一样，我们也可以继续迭代下去。

这样就可以保证前面始终不降，复杂度线性。

贴一下 P3375 的代码：

:::success[code]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


#include<bits/stdc++.h>
using namespace std;
int nxt[2000005];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
	string s1,s2;
	cin>>s1>>s2;
	int n=s1.length(),m=s2.length();
	s1=' '+s1;
	s2=' '+s2;
	int p=0;
	nxt[1]=0;
	for(int i=2;i<=m;i++){
		while(p&&s2[i]!=s2[p+1])p=nxt[p];
		if(s2[i]==s2[p+1])p++;
		nxt[i]=p;
	}
	int j=0;
	for(int i=1;i<=n;i++){
		while(s1[i]!=s2[j+1]&&j)j=nxt[j];
		if(s1[i]==s2[j+1])j++;
		if(j==m){
			cout<<i-j+1<<'\n';
			j=nxt[j];
		}
	}
	for(int i=1;i<=m;i++)cout<<nxt[i]<<' ';
}

:::

学会了 ^_^。