顺序和逆序读起来完全一样的串叫做回文串。比如 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 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             #define ll long longusing namespace std;const int maxn=1e6+20;char str[maxn];int len1,len2,ans,f[maxn];void init(char s[]){ str[0]='$'; str[1]='#'; for(int i=0; i
              
               i) p[i] =min(p[2*id-i],mx-i); else p[i]=1; 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,0,sizeof(f)); Manacher(p); ans=0; for(int i=1; i