P4840 P哥旋转 题解

· · 题解

可以看得出来本题就是求把原串复制一遍后求每个长度为 n 的子串的本质不同回文字串的最大值。

于是可以直接 区间本质不同回文字串。

但是数据范围不行，于是考虑直接维护一个动态回文自动机，可以开头删和尾部加。

对于开头可以和尾部维护最大回文后缀一样维护每个位置开头的最大回文前缀。而删除开头的字符后如果回文树不会变化，那么这个位置开头的最大回文前缀一定在后面出现过。于是可以对于尾部加入的字符暴力跳 fail 修改每个可行的回文后缀的最大出现时间。

因为题目上写明的数据水所以可以过，不过应该可以离线下来用线段树维护。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;char s[3000010];int ed[3000010],pt[3000010];
int t[3000010][26],is[3000010],ln[3000010],to[3000010],idx,n,res,ans;
int find(int p,int i,int x){while(i-ln[p]-1<x||s[i]!=s[i-ln[p]-1])p=to[p];return p;}
int main(){
    scanf("%s",s+1),n=strlen(s+1);
    ln[0]=0,ln[1]=-1,to[0]=1,to[1]=-1,idx=1;
    for(int i=1;i<=n;i++)s[i+n]=s[i]-='a';
    for(int i=1,p=0;i<=(n<<1);i++){
        if(i>n&&i-n+ln[is[i-n]]-1==ed[is[i-n]]){
            t[pt[is[i-n]]][s[i-n]]=0,res--;
            if(is[i-n]==p)p=to[p];
        }
        p=find(p,i,max(1,i-n+1));
        if(!t[p][s[i]]){
            to[++idx]=t[find(to[p],i,max(1,i-n+1))][s[i]],res++;
            ln[idx]=ln[p]+2,t[p][s[i]]=idx,pt[idx]=p;
        }p=t[p][s[i]],ans=max(ans,res);
        for(int q=p;~q;q=to[q])ed[is[i-ln[q]+1]=q]=i;
    }
    cout<<ans;return 0;
}

好像官方正解好像也是O(玄学)的。