题解 CF432D 【Prefixes and Suffixes】

题目链接

Solution CF432D Prefixes and Suffixes

题目大意：给定一个字符串，求所有既是前缀又是后缀的字符串的长度，以及其在字符串中出现次数

KMP算法

---

分析：首先既是前缀又是后缀就是KMP算法中(pi)函数的定义，于是我们可以对原字符串跑KMP，假定长度为(n)，那么(pi[n-1])就是最长的既是前缀也是后缀的字符串（整个字符串我们特判一下）

然后我们要快速的求出下一个既是前缀也是后缀的字符串，根据(pi)函数的性质，长为(pi[n-1])的后缀一定对应着(pi[n-1])的前缀，那么我们找长度为(pi[n-1])的前缀这个字符串中，既是前缀也是后缀的字符串就可以了，这是原问题的子问题

然后问题变成了给一个字符串，统计每一个前缀出现了多少次

我们继续挖掘(pi)函数的性质

对于任意位置(i)，以它结尾的前缀有(pi[i]),(pi[pi[i]-1]),(pi[pi[pi[i]-1]-1])等等，但是显然我们不能暴力计算

我们考虑假如已经知道有长为(i)的前缀出现次数(ans[i])，我们考虑其对答案的贡献，它对长为(pi[i-1]),(pi[pi[i-1]-1]),(pi[pi[pi[i-1]-1]-1])等等的前缀都有贡献，同样不用暴力计算，我们只需要将其的贡献累加到(pi[i-1])即可

然后每个长度的前缀的出现次数(+1)，因为其作为前缀的出现次数也要累计入答案

数组下标从(0)开始叙述会方便点？

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int maxn = 1e6 + 100;
char s[maxn];
int n,pi[maxn],ans[maxn];
inline void build(){
	for(int i = 1;i < n;i++){
		int j = pi[i - 1];
		while(j && s[i] != s[j])j = pi[j - 1];
		if(s[i] == s[j])j++;
		pi[i] = j;
	}
	for(int i = 0;i < n;i++)ans[pi[i]]++;
	for(int i = n - 1;i > 0;i--)ans[pi[i - 1]] += ans[i];
	for(int i = 0;i <= n;i++)ans[i]++;
}
vector<pair<int,int>> ansout;
int main(){
	scanf("%s",s);
	n = strlen(s);
	build();
	int now = pi[n - 1];
	while(now){
		ansout.push_back(make_pair(now,ans[now]));
		now = pi[now - 1];
	}
	reverse(ansout.begin(),ansout.end());
	ansout.push_back(make_pair(n,1));
	printf("%d
",(int)ansout.size());
	for(auto x : ansout)
		printf("%d %d
",x.first,x.second);
	return 0-0;
}