线性PAM的神仙们tql，蒟蒻只会manacher
考虑双倍回文串本身一定也是一个回文串，我们在manacher计算的过程中，一共只会产生 \(O(n)\) 个本质不同的回文串。
实际上，我们每次只需要计算新出现的那些回文串。归纳地去证明，如果一个子串不是新出现的，它关于 \(mid\)（就是manacher中，那个在计算 \(i\) 之前 \(p[j]+j\) 最远的那个 \(j\)）一定有一个对称的串，在那个对称串，相似的，要么继续对称往前，总会遇到一次，是新出现的，此时这一连串个对称的相同的串都被计算了。所以我们每次只计算新产生的那些回文串。
首先，注意到双倍回文串长度是 \(4\) 的倍数，所以我们只能在当前字符为特殊字符（本文用 '#' 字符）时才更新答案。
显然，我们可以 \(O(1)\) 判断 \(S[x,y]\)（以 \(i\) 为中心）是否回文，\(O(1)\) 计算 \(S[x,y]\) 的真实字符个数。（这个不用讲）
判断 \(S[x,y](mid:i)\) 是否合法，首先计算出字符个数判断其是否为 \(4\) 的倍数，然后，注意到 \(S[x,y]\) 本身回文，只需要证明左半部分或者右半部分回文即可。因为我们还没算出右半部分的答案，所以我们判断左半部分是否回文。此时我们需要快速找到左半部分中间点，然后判断这个中心点 \(pos\) 的 \(p[pos]\) 是否大于等于左半部分长度即可。（细节较多注意不要写挂）
//SHOI,2011
#include<bits/stdc++.h>
#define rep(i,a,b) for(ll i=(a);i<=(b);i++)
#define per(i,a,b) for(ll i=(a);i>=(b);i--)
#define next Cry_For_theMoon
#define il inline
typedef long long ll;
using namespace std;
const int MAXN=1e6+10;
int n,ans,p[MAXN],pos,r;
char str[MAXN],tmp;
int main(){
scanf("%d",&n);
rep(i,1,n){
scanf(" %c",&tmp);
str[i*2]=tmp;
str[i*2+1]='#';
}
str[1]='#';
n=n*2+1;
rep(i,1,n){
if(i<=r)p[i]=min(r-i,(ll)p[pos*2-i]);
while(i-p[i]>=1&&i+p[i]<=n&&str[i-p[i]]==str[i+p[i]])p[i]++;
p[i]--;
if(i+p[i]>r){
if(str[i]=='#'){
rep(j,max(i+4,(ll)r),i+p[i]){
int len=j-i;
if((len)%4)continue;
if(p[i-len/2]>=len/2)ans=max(ans,len);
}
}
pos=i,r=i+p[i];
}
}
printf("%d",ans);
return 0;
}