BZOJ2342 Shoi2011 双倍回文

#include<bits/stdc++.h>
using namespace std;
#define N 500010
char t[N],s[N<<1];
int n=0,len;
int p[N<<1],g[N<<1];
void Manacher(){
    int pos=0,x=0,id=0;
    for(int i=1;i<n;i++){
        if(pos>i)x=min(p[id*2-i],pos-i+1);
        else x=0;
        while(s[i-x]==s[i+x])x++;
        x--;
        if(i+x>pos)pos=i+x,id=i;
        p[i]=x;
    }
}
int main(){
    scanf("%d%s",&len,t);
    s[0]=‘!‘;
    for(int i=0;i<len;i++){
        s[++n]=‘#‘;
        s[++n]=t[i];
    }
    s[++n]=‘#‘;
    s[++n]=‘?‘;
    Manacher();
    int ans=0;
    for(int i=0;i<n;++i)
	     g[i]=p[2*i+1]/2;
    for(int i=0;i<n;++i)
        for(int j=g[i]/2;j&&j*4>ans;j--)
            if(g[i+j]>=j&&g[i-j]>=j)ans=max(ans,4*j);
    printf("%d",ans);
    return 0;
}
zz https://blog.csdn.net/dream_maker_yk/article/details/80804663