Description
Input
输入分为两行，第一行为一个整数，表示字符串的长度，第二行有个连续的小写的英文字符，表示字符串的内容。
Output
输出文件只有一行，即：输入数据中字符串的最长双倍回文子串的长度，如果双倍回文子串不存在，则输出0。
Sample Input
16
ggabaabaabaaball
Sample Output
12
HINT
N<=500000
本题是一道Manacher思维好题。考虑暴力的做法，由于答案串一定形如 $ WW^RWW^R $那么我们枚举一个 i 表示整个串的中点，同时枚举 j 表示一个小串的中点，则有 p[j]+j>=x。这个不难理解，否则 p[j]+j < x 的话，我们怎么保证中间缺的一部分回文呢？同时，j 的范围为[i-p[i]/2,i)，不然枚举出来的回文串长度会不够
不过这样寻找肯定是超时的。因为要使答案最优，我们肯定是找到满足条件的一个最小的 j ，因此当某个 j 不符合条件的话，我们就没必要再考虑它了
于是我们就可以用set，并查集，树状数组随便搞搞就过去了
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define inf 0x7f7f7f7f
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
inline int read(){
int x=0,f=1;char ch=getchar();
for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1;
for (;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+ch-'0';
return x*f;
}
inline void print(int x){
if (x>=10) print(x/10);
putchar(x%10+'0');
}
const int N=5e5;
char s[N*2+10];
int p[N*2+10],fa[N*2+10];
int find(int x){
if (x==fa[x]) return x;
return fa[x]=find(fa[x]);
}
int main(){
int len=read();
scanf("%s",s+1);
for (int i=len;i;i--) s[i<<1]=s[i],s[i<<1|1]='&';
len=len<<1|1;
s[0]='#',s[1]='&',s[len+1]='^';
int Max=0,ID=0,ans=0;
for (int i=1;i<=len;i++){
p[i]=Max>i?min(p[ID*2-i],Max-i):1;
while (s[i+p[i]]==s[i-p[i]]) p[i]++;
if (Max<p[i]+i) Max=p[ID=i]+i;
}
for (int i=1;i<=len;i++) s[i]=='&'?fa[i]=i:fa[i]=i+1;//因为答案串一定是偶串，所以fa要指向'&'
for (int i=1;i<=len;i+=2)//偶串的原因
for (int j=find(max(i-p[i]/2,1));j<i;fa[j]=find(j+1),j=fa[j])
if (j+p[j]>i){ans=max(ans,(i-j)*2);break;} //并查集查找优化
printf("%d
",ans);
return 0;
}