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\n",(int)ansout.size());
    for(auto x : ansout)
        printf("%d %d\n",x.first,x.second);
    return 0-0;
}

前缀

题解 CF432D 【Prefixes and Suffixes】

Solution CF432D Prefixes and Suffixes