KMP-前缀函数

这里字符串下标默认从开始。

STY_fish_2012

38人浏览 · 2026-06-05 21:02:08

STY_fish_2012 · 2026-06-05 21:02:08 发布

这里字符串下标默认从 1 开始。

前缀函数

一些概念

前缀：一个字符串通过从结尾删除字符得到的子串（可以不删）。
后缀：一个字符串通过从开头删除字符得到的子串（可以不删）。
真前缀：一个字符串通过从结尾删除字符得到的子串（必须删）。
真后缀：一个字符串通过从开头删除字符得到的子串（必须删）。

$\pi$

定义对于字符串 $s$ 的 $\pi$ 数组， $\pi_i$ 表示前缀 $[1, i]$ 的最长真前缀（且有一个后缀与之相等）长度，这个真前缀称为 border。

求法

暴力
先看一个 $O(N^3)$ 的暴力：

for(int i=2;i<=n;i++){
		for(int j=i-1;j>=1;j--){
			if(s.substr(1,j)==s.substr(i-j+1,j)){
				p[i]=j;
				break;
			}
		}
	}

没有任何优化，纯暴力。

优化 1

注意到在最好的情况下， $\pi_i$ 的值每次最多增加 1，所以当前最大的情况也就是 $\pi_{i-1}+1$ 。

for(int i=2;i<=n;i++){
		for(int j=p[i-1]+1;j>=1;j--){
			if(s.substr(1,j)==s.substr(i-j+1,j)){
				p[i]=j;
				break;
			}
		}
	}

这样看似没有改变什么，但实际的时间复杂度是 $O(N^2)$ 的了。

因为每次增加 1， $\pi_i$ 的最大值也只会到达 $n - 1$ ，而下限是 0，所以外面两层枚举的总时间复杂度是 $O (N)$ 的。

优化 2

注意到 $\pi_i$ 的定义，有 $[1,\pi_i]=[i-\pi_i+1,i]$ 。
在这里插入图片描述
上图中，蓝色部分就是 $[1,\pi_i]$ 和 $[i-\pi_i+1,i]$ ，右边的黄色部分就是新加入的 $i + 1$ 。

若要使新的 $\pi_{i+1}=\pi_i+1$ ，则需要两个黄色部分的字符相同。

但是如果不相同怎么办？

我们将目光转移到 $\pi_{\pi_i}$ 上面。由于 $[1,\pi_i]=[i-\pi_i+1,i]$ ，还有 $[1,\pi_{\pi_i}]=[\pi_i-\pi_{\pi_i}+1,\pi_i]$ ，所以一定有 $[1,\pi_{\pi_i}]=[i-\pi_{\pi_i}+1,i]$ ，这时候还是可以将 $[1,\pi_{\pi_i}]$ 和 $[i-\pi_{\pi_i}+1,i]$ 两个区间视为上图中的蓝色部分，此时若黄色部分的字符相同，就有 $\pi_{i+1}=\pi_{\pi_i}+1$ 。

那如果还是不同怎么办？

就继续看 $\pi_{\pi_{\pi_i}}$ ，直到没有为止。

时间复杂度 $O (N)$ ，可以像【优化 1】中的那样分析。

for(int i=2;i<=n;i++){
	int j=p[i-1];
	while(j&&s[j+1]!=s[i])j=p[j];
	if(s[j+1]==s[i])j++;
	p[i]=j;
}

那为什么这样一定是对的？

首先正确性是毋庸置疑的。

看到最优性。根据 $\pi$ 的定义，其一定是最大的，所以 $\pi_{\pi_i}$ 一定是 $\pi_i$ 的所以满足条件的前缀中最大的一个， $\pi_{\pi_{\pi_i}}$ 以此类推。

既然是从最大的开始向更小的找，那么肯定没有遗漏。

字符串匹配

所以 KMP 到底是啥？

其实没有前缀函数的 $O (N)$ 求法，KMP 啥都不是。

查询模式串 $s_2$ 在文本串 $s_1$ 出现的位置。

题目：P3375 【模板】KMP

方案一

既然前缀函数是求一个前缀的 border 长度，那么我们只需要让模式串称为那个固定的前缀，去匹配文本串中的子串。

那么怎么找文本串的子串呢？前缀的后缀就是一个子串。

所以我们将两个字符串拼接起来：
$s=s_2+"\#"+s_1$
中间的 $\#$ 是为了防止匹配的长度超过模式串。

这时候我们遍历过程中，就会找到文本串 $s_1$ 的每个前缀，并且通过 $\pi_i$ 数组得到其与模式串的前缀相同的后缀。

当 $\pi_i$ 的值等于模式串 $s_1$ 的长度时，就说明匹配成功了。

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+5;//字符串要拼接，要开两倍空间
int m;
int p[N];
signed main(){
	string s1,s2;
	cin>>s1;
	cin>>s2;
	m=s2.length();
	string s=" "+s2+"#"+s1;
	for(int i=2;i<s.size();i++){
		int j=p[i-1];
		while(j&&s[j+1]!=s[i])j=p[j];
		if(s[j+1]==s[i])j++;
		p[i]=j;
	}
	for(int i=m+2;i<s.size();i++){
		if(p[i]==m){
			cout<<i-2*m<<'\n';
		}
	}
	for(int i=1;i<=m;i++)cout<<p[i]<<' ';
}

方案二

直接比较。

先得求出模式串 $s_2$ 对应的 $\pi$ 数组。

用两个指针 $i$ 和 $j$ 分别在文本串 $s_1$ 和模式串 $s_2$ 中标记匹配位置。

若 ${s_1}_i=={s_2}_{j+1}$ ，那么两个指针各自加一即可。

若不相等，则需要将指针 $j$ 回移。

在这里插入图片描述
与求前缀函数的【优化 2】类似，蓝色部分即为模式串 $s_2$ 中 $[1, j]$ 的 border。

当匹配不上时，为了防止时间爆炸，要用上之前已经匹配过的地方。所以将 $j$ 变为 $\pi_j$ 。由于两端蓝色部分相同，所以不会影响前面的匹配。同理，若还是不匹配，则转到 $\pi_{\pi_j}$ 。

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+5;
int n,m;
int p[N];
signed main(){
	string s1,s2;
	cin>>s1;
	cin>>s2;
	n=s1.length(),m=s2.length();
	s1=" "+s1;
	s2=" "+s2;
	for(int i=2;i<=m;i++){
		int j=p[i-1];
		while(j&&s2[j+1]!=s2[i])j=p[j];
		if(s2[j+1]==s2[i])j++;
		p[i]=j;
	}
	int j=0;
	for(int i=1;i<=n;i++){
		while(j&&s2[j+1]!=s1[i])j=p[j];
		if(s2[j+1]==s1[i])j++;
		if(j==m){
			cout<<i-m+1<<'\n';
			j=p[j];
		}
	}
	for(int i=1;i<=m;i++)cout<<p[i]<<' ';
}

其他应用

字符串的周期

字符串 $s$ 的周期 $t$ 通过重复若干次可以得到一个字符串 $S$ ，使得 $s$ 是 $S$ 的前缀。

第一种情况：border 未重叠
在这里插入图片描述
此时的周期很明显就是长度为 $n-\pi_n$ 的 $[1,n-\pi_n]$ 和 $[\pi_n+1,n]$ 了。
第二种情况：border 重叠

上图中两个黑框框就是两个 border。根据 border 的定义，有两个橙色部分，两个蓝色部分相同。