题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=2342
思路：先跑一遍Manacher求出p[i]为每个位置为中心的回文半径，因为双倍回文串的长度一定是4的倍数，即偶数，那么对于Manacher的回文中心一定是'#'字符。所以我们枚举每个'#'，对于每个'#'当回文半径大于等于4才有可能成为双倍回文。如果当前位置的i是'#'且满足以上条件。那么我们就找到i右边的j。因为双倍回文的长度是4的倍数，那么i右边的j的回文长度一定是2的倍数，即偶数，所以对于j我们只需要枚举等于'#'的j，然后如果p[j]>j-i即说明了存在一个长度为(j-i)*2的双倍回文串。因为i是双倍回文的中心，j又是i右边回文串的中心，所以j的枚举范围是[i,i+(p[i]/2)]. 注意暴力判断j时需要j从大到小判断，当找到第一个满足双倍回文的j时就要跳出枚举。因为此时的j肯定是最长的。不然会TLE。
#define _CRT_SECURE_NO_DEPRECATE
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
using namespace std;
const int MAXN = + ;
typedef long long int LL;
#define INF 0x3f3f3f3f
char str[MAXN], dstr[MAXN * ];
int lenstr, lendstr, p[MAXN * ], ans;
void manacher(){
memset(p, , sizeof(p));
int id = , mx = ;
for (int i = ; i<lendstr; i++){
if (mx>i){
p[i] = min(p[ * id - i], mx - i);
}
else{
p[i] = ;
}
while (dstr[i - p[i]] == dstr[i + p[i]]){ //暴力匹配
p[i]++;
}
if (p[i] + i>mx){
mx = p[i] + i;
id = i;
}
}
}
void init(){
dstr[] = '$';
dstr[] = '#';
for (int i = ; i<lenstr; i++){
dstr[i * + ] = str[i];
dstr[i * + ] = '#';
}
lendstr = lenstr * + ;
dstr[lendstr] = '*';
}
int main()
{
int n;
while (~scanf("%d", &n)){
scanf("%s", str);
lenstr = n;
init();
manacher();
ans = ;
for (int i = ; i < lendstr; i++){//实际回文长度为p[i]-1
p[i]--;
}
for (int i = ; i<lendstr; i++){
if (dstr[i] == '#'&&p[i]>=){//枚举每一个'#'并且半径大于等于4的i
for (int k = p[i] / ,j=i+k*; k >; k--, j -= ){//枚举j，j为i右边的'#'
if (p[j] >= j - i){
ans = max(ans, (j-i) * );
break; //剪枝。
}
}
}
}
printf("%d\n", ans);
}
return ;
}