P4840 P哥旋转 题解

· · 题解

思路

前置知识：回文自动机。

首先破环为链，复制一份 s，变成了问 [1,n] 到 [n-1,2n-1] 中每个区间的最大本质不同回文子串个数。回文自动机他有一个重要的性质，那就是回文自动机的每个节点，代表了本质相同的一些回文子串。于是我们可以记录一个 cnt 数组，表示每个点（对应的那个回文子串）出现了多少次，答案就是 cnt>0 的点数。

在加入一个字符时，通过跳一遍 fail 找到所有以它结尾的回文串，将这些点加一，然后我们需要在 i-len_x+n 的位置将它减回去。其中 x 是所有回文后缀结点。用一个堆维护这个信息即可。

注意，我们只计算长度小于等于 n 的子串（因为我们复制了一份原字符串，所以可能会存在由两个原串拼成的回文串，这是不能被计算的），跳 fail 时需要注意这一点。

注意到数据随机，所以 fail 树上的点深度基本都很低，于是复杂度不会很高。

代码

#include<bits/stdc++.h>
using namespace std;
constexpr int N=3e6+5;
int n,len[N],cnt[N],fail[N],trie[N][26],tot=1;
string s;
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > Q;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>s,n=s.size(),s='$'+s+s;
    len[0]=0,fail[0]=1;
    len[1]=-1,fail[1]=0;
    int ans=0,last=1,sub=0;
    for(int i=1;i<=2*n-1;i++){
        while(!Q.empty()&&Q.top().first+n-1<i){
            int q=Q.top().second;
            cnt[q]--;
            if(cnt[q]==0)sub--;
            Q.pop();
        }
        int fa=last;
        while(len[fa]>n-2||s[i]!=s[i-len[fa]-1])fa=fail[fa];
        int &v=trie[fa][s[i]-'a'];
        if(!v){
            ++tot;
            int tmp=fail[fa];
            while(s[i]!=s[i-len[tmp]-1])tmp=fail[tmp];
            tmp=trie[tmp][s[i]-'a'];
            v=tot;
            fail[v]=tmp;
            len[v]=len[fa]+2;
        }
        for(int q=v;q>=2;q=fail[q]){
            if(cnt[q]==0)sub++;
            cnt[q]++;
            Q.push(make_pair(i-len[v]+1,q));
        }
        last=v;
        ans=max(ans,sub);
    }
    cout<<ans;
    return 0;
}