输入分为两行，第一行为一个整数，表示字符串的长度，第二行有个连续的小写的英文字符，表示字符串的内容。
输出文件只有一行，即：输入数据中字符串的最长双倍回文子串的长度，如果双倍回文子串不存在，则输出0。
N<=500000
先把每个回文中心对应的最长回文串长搞出来 正常manacher
然后 枚举回文中心 暴力寻找双倍回文
跑的很快的
然而虽然用以上方法A了题 这并不是我的做法
因为没A掉所以只能提供一种思路
希望有神犇用这个方法A掉 然后来指导蒟蒻QwQ
在维护manacher的时候同时维护以每个字符为结尾的最长回文串长度
寻找双倍回文时
暴力枚举回文中心（过程中保证回文串长为偶数）
然后只需要判一下它前一个字符为结尾的最长回文串长度和以该字符为回文中心的最长回文串长度哪个小
就用小的更新答案
本蒟蒻觉得解法很优 但没调过 一定要有神犇解救啊啊
#include<cmath> #include<ctime> #include<cstdio> #include<cstring> #include<cstdlib> #include<complex> #include<iostream> #include<algorithm> #include<iomanip> #include<vector> #include<string> #include<bitset> #include<queue> #include<map> #include<set> using namespace std; typedef long long ll; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch<='9'&&ch>='0'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x*f; } void print(int x) {if(x<0)putchar('-'),x=-x;if(x>=10)print(x/10);putchar(x+'0');} const int N=1000100; char ch[N],s[N]; int p[N],f[N]; int main() { int n=read(); scanf("%s",ch+1); register int i,j,maxn,d,ans,tmp; for(i=1;i<=n;++i)s[i<<1]=ch[i],s[(i<<1)-1]='#';s[(n<<1)+1]='#';s[0]='!'; n<<=1;maxn=d=ans=0; for(i=1;i<=n;i+=2) { i<maxn?p[i]=min(maxn-i,p[(d<<1)-i]):p[i]=1; while(s[i-p[i]]==s[i+p[i]])p[i]++; if(i+p[i]>maxn){maxn=i+p[i];d=i;} } for(int i=1;i<n;i+=2) { j=p[i]>>1;if(j&1)j--; for(;j&&j*2>ans;j-=2) if(p[i-j]>j&&p[i+j]>j)ans=j<<1; } print(ans);puts("");return 0; } /* 16 ggabaabaabaaball 12 */
