shoi题目好坑爹
首先自己测发现这道题如果用后缀数组+rmq处理每个点回文串能延伸长度的话会TLE
（当然我用的是倍增+ST的方法，如果用三分构建后缀数组+笛卡尔树处理rmq我就不知道了）；
关于最长回文子串的问题有一个更快的算法叫manacher，实现简单也好理解
这个算法的优点在于它在每两个字符之间插入一个新的字符#，使得所有的回文子串都变成了奇数长度的
具体的介绍：http://blog.****.net/ggggiqnypgjg/article/details/6645824
求出以每个字符为中心的回文串最长延伸长度p[i]后（注意p[i]-1就是在原串中以该字符为中心的最长回文子串）
我们下面就要来找双倍回文
首先，穷举中心字符我们肯定是穷举“#”而不穷举字母
不难想到一种O(n2)的做法，先穷举双倍回文的中心，在穷举左半边回文的中心判断是否存在可行解
（事实上，左边穷举的时候我们只要从i-p[i]/2找就可以了
但实际上，随着我们向右穷举双倍回文的中心，左边一些点穷举了一次是肯定是不用再穷举的，
我们可以考虑用并查集优化
var p,fa:array[..] of longint;
j,l,n,k,i,ans,right:longint;
s:array[..] of char;
ch:char; function min(a,b:longint):longint;
begin
if a>b then exit(b) else exit(a);
end; function max(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end; function getf(x:longint):longint;
begin
if x<>fa[x] then fa[x]:=getf(fa[x]);
exit(fa[x]);
end; begin
readln(l);
s[]:='$';
s[]:='#';
for i:= to l do
begin
read(ch);
s[i*]:=ch;
s[i*+]:='#';
end;
n:=*l+;
k:=;
right:=;
for i:= to n do
begin
if right>i then
p[i]:=min(p[*k-i],right-i)
else p[i]:=;
while (s[i+p[i]]=s[i-p[i]]) do inc(p[i]);
if p[i]+i>right then
begin
right:=p[i]+i;
k:=i;
end;
end;
for i:= to n do
if s[i]='#' then fa[i]:=i else fa[i]:=i+;
for i:= to n do
begin
if i mod = then
begin
j:=getf(max(i-p[i] div ,));
while (j<i) and (j+p[j]-<i) do
begin
fa[j]:=getf(j+);
j:=fa[j];
end;
if j<i then ans:=max(ans,(i-j)*);
end;
end;
writeln(ans);
end.