BZOJ 2565: 最长双回文串 [Manacher]

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=3e5+5;
typedef long long ll;
int n;
char s[N],str[N];
int r[N];
void Manacher(char s[],int n){
    int p=0,a;
    for(int i=1;i<=n;i++){
        r[i]=i<p?min(p-i+1,r[2*a-i]):1;
        while(s[i-r[i]]==s[i+r[i]]) r[i]++;
        if(i+r[i]-1>p) p=i+r[i]-1,a=i;
    }
}
void iniStr(char str[],char s[]){
    for(int i=1;i<=n;i++)
        s[(i<<1)-1]=‘#‘,s[i<<1]=str[i];
    s[n<<1|1]=‘#‘;
    s[0]=‘@‘;s[(n<<1)+2]=‘$‘;
}
int l[N];
int main(){
    freopen("in","r",stdin);
    scanf("%s",str+1);
    n=strlen(str+1);
    iniStr(str,s);
    Manacher(s,n<<1|1);
    n=n<<1|1;
    int now=1,ans=0;
    for(int i=1;i<=n;i++){
        while(now+r[now]-1<i) now++;
        l[i]=now;
    }
    now=n;
    for(int i=n;i>=1;i--){
        while(now-r[now]+1>i) now--;
        if(i&1) ans=max(ans,now-l[i]);
    }
    printf("%d",ans);
}