顺序和逆序读起来完全一样的串叫做回文串。比如 acbca 是回文串，而 abc 不是（ abc 的顺序为 “abc” ，逆序为 “cba” ，不相同）。
输入长度为
n
的串
S
，求
S
的最长双回文子串
T,
即可将
T
分为两部分
X
，
Y
，（
|X|,|Y|≥1
）且
X
和
Y
都是回文串。
Input
一行由小写英文字母组成的字符串S。
Output
一行一个整数，表示最长双回文子串的长度。
Sample Input
baacaabbacabb
Sample Output
12
样例说明
从第二个字符开始的字符串aacaabbacabb可分为aacaa与bbacabb两部分，且两者都是回文串。
对于100%的数据，2≤|S|≤10^5
网上几乎都是用回文树写的，改日学学，网上其他Manacher写的也感觉挺麻烦的，还有开L【】 R【】两个数组来弄的。
emmm，用一个F【】临时存存就好了呀。
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <map>
#define ll long long
using namespace std;
const int maxn=1e6+; char str[maxn];
int len1,len2,ans,f[maxn]; void init(char s[])
{
str[]='$';
str[]='#';
for(int i=; i<len1; i++)
{
str[i*+]=s[i];
str[i*+]='#';
}
len2=len1*+;
str[len2]='*';
} void Manacher(int p[])
{
int id=,mx=;
for(int i=; i<len2; i++)
{
if(mx>i) p[i] =min(p[*id-i],mx-i);
else p[i]=;
if(!f[i]) f[i]=i;
for(; str[i-p[i]]==str[i+p[i]]; p[i]++)
{
if(!f[i+p[i]]) f[i+p[i]]=i;
}
if(p[i]+i>mx)
{
mx=p[i]+i;
id=i;
}
}
}
char s[maxn];
int p[maxn];
int main()
{ while(cin>>s)
{
len1=strlen(s);
init(s);
memset(f,,sizeof(f));
Manacher(p);
ans=;
for(int i=; i<len2; i++)
{
// printf("i=%d str=%c p[i]=%d f[i-p[i]]=%d\n",i,str[i],p[i],f[i-p[i]]);
ans=max(ans,i-f[i-p[i]]);
}
cout<<ans<<endl;
}
return ;
}