Description

Input

输入分为两行，第一行为一个整数，表示字符串的长度，第二行有个连续的小写的英文字符，表示字符串的内容。

Output

输出文件只有一行，即：输入数据中字符串的最长双倍回文子串的长度，如果双倍回文子串不存在，则输出0。

Sample Input

16

ggabaabaabaaball

Sample Output

12

HINT

N<=500000

Source

思路

显然每个双倍回文串被扩充（插入字符）后的结果一定是$A$AR$A$AR$，那么以第3个$为中心的整个串一定是回文串，以第2个$为中心的串的前半部分和以第4个$为中心的串的后半部分串也是回文串。那么可以依据这两个性质进行计算了：

1. 枚举中心点i。

2. j为回文串能够包含于i为中心的回文串的最小节点序号。

3. 如果以j为中心的回文串可以到达i，那么更新ans值；否则删除j，并将j赋值为j右侧可以到达的第一个没有被删除的点，然后重复这个步骤。

但是上面这个步骤显然是不能过的，时间复杂度为O(n2)，这个时候显然可以用并查集来优化了。

代码

#include 
    
     #include 
     
      const int maxn=500000;char s[maxn+10],a[(maxn<<1)+10];int p[(maxn<<1)+10],id,rmax,k,n,ans;int fa[(maxn<<1)+10];int find(int x){  if(fa[x])    {      return fa[x]=find(fa[x]);    }  else    {      return x;    }}int main(){  scanf("%d%s",&n,s+1);  a[0]='!';  a[1]='$';  for(register int i=1; i<=n; ++i)    {      a[i<<1]=s[i];      a[i<<1|1]='$';    }  n=n<<1|1;  a[n+1]='*';  id=rmax=p[1]=1;  for(register int i=2; i<=n; ++i)    {      if(i>rmax)        {          p[i]=1;        }      else        {          if(p[(id<<1)-i]
      
       rmax)        {          rmax=i+p[i]-1;          id=i;        }    }  for(register int i=1; i<=n; i+=2)//寻找中心点    {      int j;//j代表左半部分的中心点      if(i-(p[i]>>1)>1)        {          j=i-(p[i]>>1);        }      else        {          j=1;        }      j=find(j);//最右侧没有被删除的节点      while((j
       
        
         ans)            {              ans=(i-j)<<1;//更新ans            }        }    }  printf("%d\n",ans);  return 0;}