2342: [Shoi2011]双倍回文

Time Limit: 10 Sec  Memory Limit: 128 MB

Submit: 1799  Solved: 671

[][][]

Description

Input

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

Output

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

Sample Input

16

ggabaabaabaaball

Sample Output

12

HINT

N<=500000

Source

Solution

看完题大体的思路就是先一遍Manacher,O(n)求出回文串,然后进行判断

题目中说的很清楚,双倍回文串长度一定是4的倍数,即为偶数,那么Manacher出来的回文串中心一定在字符间添加的'#'上

那么考虑要求的东西 y+p[y]>=x && y>=x-p[x]/2,思考一个枚举的方法

枚举j,如果j不能覆盖到当前的i,那么一定是不符合覆盖到i+1的,所以,之后的所有事和它无关,可以忽略,这样想,维护一下就好了,采取并查集

Code

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;#define maxn 500010char S[maxn],s[maxn<<1];int n,len,mx,id,p[maxn<<1],fa[maxn<<1],ans;void PreWork(){    memset(p,0,sizeof(p));    len=n<<1|1;    for (int i=1; i<=n; i++)        s[i<<1]=S[i],s[i<<1|1]='#';    s[0]='$'; s[1]='#'; s[len+1]='%';}void Manacher(){    PreWork();    for (int i=1; i<=len; i++)        {            if (mx>i) p[i]=min(p[id*2-i],mx-i);                else p[i]=1;            while (s[i-p[i]]==s[i+p[i]]) p[i]++;            if (p[i]+i>mx) mx=p[i]+i,id=i;        }}int find(int x) {
   if (fa[x]==x) return x; else return fa[x]=find(fa[x]);}int main(){    scanf("%d",&n); scanf("%s",S+1);    Manacher();    for (int i=1; i<=len; i++)        if (s[i]=='#') fa[i]=i; else fa[i]=i+1;    for (int i=3; i<=len-1; i+=2)        {            int f=find(max(i-p[i]/2,1));            while (f
          ans) ans=(i-f)*2; } printf("%d\n",ans); return 0;}