题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5371
这道题用到了Manacher算法，首先简单介绍一下Manacher算法：
----------------------------------------------------------------------------------------------
【转】http://blog.csdn.net/yzl_rex/article/details/7908259
一个专门针对回文子串的算法，其时间复杂度为O(n)
求回文串时需要判断其奇偶性，也就是求aba 和abba 的算法略有差距。然而，这个算法做了一个简单的处理，
很巧妙地把奇数长度回文串与偶数长度回文串统一考虑，也就是在每个相邻的字符之间插入一个分隔符，
串的首尾也要加，当然这个分隔符不能再原串中出现，一般可以用‘#’或者‘$’等字符。
这样一来，原来的奇数长度回文串还是奇数长度，偶数长度的也变成以‘#’为中心奇数回文串了。
接下来就是算法的中心思想，用一个辅助数组P 记录以每个字符为中心的最长回文半径，
也就是P[i]记录以Str[i]字符为中心的最长回文串半径。P[i]最小为1，此时回文串为Str[i]本身。
核心代码：
if (maxid > i){
p[i] = min(p[*id - i], maxid - i);
}
-----------------------------------------------------------------------------------------------
再回到本题，因为所给的数列为非负整数，所以用-1作为间隔，利用Manacher算法求出各点的最长回文，
然后因为 abbaab 可以理解为 abba 和 baab 两个回文串，所以在第一个回文串的末尾往回找，
如果回文串的长度大于两点之间的距离，且大于sum，则更新sum。
在遍历过程中进行简化，易知回文串必然是偶数个的，所以只遍历-1的点就可以了。
#include<stdio.h>
#include<algorithm>
#include<cstring>
using namespace std;
;
int str[MAXN];
int p[MAXN];
int N;
int main(){
int T;
;
int mx, pi;
int _max;
int j;
scanf("%d",&T);
while(T--){
memset(p,,sizeof(p));
memset(str,,sizeof(str));
str[] = -;
str[] = -;
scanf("%d",&N);
getchar();
N = N * + ;
; i < N; i++){
== )
scanf("%d",&str[i]);
;
}
str[N++] = -;
int lgt = N;
mx = ; pi = ;
; i < lgt; i = i + ){
){
if( i < mx)
p[i] = min(p[*pi-i],mx-i);
else
p[i] = ;
while( str[i-p[i]] == str[i+p[i]])
p[i]++;
if( p[i]+i > mx ){
pi = i;
mx = p[i]+i;
}
}
}
_max = ;
; i < lgt; i = i + ){
){
;
; j - i + > _max; j -= ){
)
_max = j - i + ;
}
}
}
printf()/*);
}
}