P4555

Into_qwq · 2022-06-27 12:46:28 · 个人记录

P4555

题意：

给你一个字符串 a，求出 a 的最长 双回文子串

若一个串是 双回文子串 ，那么它可以从某个地方断开变成两个回文串

思路：

定义 p[i]：以 i 为回文中心的最长回文半径 ，l[i]：i 左侧以 i 结尾的最长回文串，r[i] 同理

先跑一遍 manacher

易得一个最长 双回文子串 必须是由两个回文串拼起来的

所以在 manacher 的时候可以通过求得的 p[i] 更新 l[i] 和 r[i]

最后在枚举一遍用 l[i]+r[i] 更新答案

注意：最后枚举更新答案时枚举的点是插进字符串的符号的位置，这样才能把左右两侧回文串拼起来

code：

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+5;

#define int long long

int n,m=2,ans;
char a[N],s[N*2];
int p[N*2],cnt[N];
int l[N*2],r[N*2];

inline void change(){
    s[0]='$',s[1]='|';
    for(int i=0;i<n;++i){
        s[m++]=a[i];
        s[m++]='|';
    }
    s[m]='%';
    n=m;
}

inline void manacher(){
    int mx=1,mid=1;
    for(int i=1;i<=n;++i){
        if(i<mx)
            p[i]=min(p[mid*2-i],mx-i);
        else
            p[i]=1;
        for(;s[i-p[i]]==s[i+p[i]];++p[i]);
        if(i+p[i]>mx){
            mx=i+p[i];
            mid=i;
        }
        l[i+p[i]-1]=max(l[i+p[i]-1],p[i]-1);
        r[i-p[i]+1]=max(r[i-p[i]+1],p[i]-1);
    }
}

signed main(){
    scanf("%s",a);
    n=strlen(a);
    m=2;
    change();
    manacher();
    for(int i=1;i<=n;i+=2)
        r[i]=max(r[i],r[i-2]-2);
    for(int i=n;i>=1;i-=2)
        l[i]=max(l[i],l[i+2]-2);
    for(int i=1;i<=n;i+=2)
        if(l[i]&&r[i])
            ans=max(ans,l[i]+r[i]);
    cout<<ans;
}