题解：P3546 [POI2012] PRE-Prefixuffix

一只绝帆 · 2024-09-04 08:44:45 · 题解

与所有题解不同的无需哈希线性做法。

首先瞪出来题目让你求的是两个 \rm border。

考虑一个非常智慧的转化：把原串按照 s_1s_ns_2s_{n-1}\cdots 这个顺序重排成一个串，你发现两个 \rm border 变成了挤在前面的两个回文串。

考虑套用 P4555 [国家集训队] 最长双回文串 的做法，直接 manacher 求回文半径，然后对能顶到序列开头的回文串标记一下末尾，再利用并查集覆盖对每个点求出最靠后的能覆盖它的回文中心，枚举回文串交界处拼一下就好。

char s[N],t[N];
int p[N],n,f[N],vis[N],res[N];
int find(int x) {return f[x]^x?f[x]=find(f[x]):x;}
int main() {
    F(i,1,n=read()) while(isspace(s[i]=gc()));
    for(int i=1,j=1;j<=n;i++,j+=2) t[j]=s[i];
    for(int i=n,j=2;j<=n;i--,j+=2) t[j]=s[i];
    t[0]='&'; 
    int mr=0,mid2=0;
    F(i,1,n-1) {//[i,i+1]
        if(mid2-i-1>0&&mr-i-1>0) p[i]=min(p[mid2-i-1],mr-i-1);
        while(t[i-p[i]]==t[i+1+p[i]]) ++p[i];
        if(i+1+p[i]>mr) mr=i+1+p[i],mid2=2*i+1;
        if(i==p[i]) vis[i+p[i]]=1; 
    }
    F(i,1,n+1) f[i]=i;
    UF(i,n-1,1) {
        for(int j=find(i-p[i]+1);j<=i;j=f[j]=find(j+1)) res[j]=i;
    }
    int ans=0;
    F(i,1,n) if(vis[i]&&res[i+1]) ans=max(ans,(res[i+1]+res[i+1]+1-(i+1))/2);
    F(i,1,n) if(vis[i]) ans=max(ans,i/2);
    cout<<ans<<endl;
    return 0;
}