Time Limit: 10 Sec  Memory Limit: 128 MB

Submit: 1915  Solved: 713

[][][]

Description

 

Input

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

 

Output

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

Sample Input

16

ggabaabaabaaball

Sample Output

12

HINT

N<=500000

 

http://hzwer.com/5375.html

算法太神以至于看不懂，先存下代码

 

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 using namespace std; 8 const int mxn=800010; 9 int p[mxn],q[mxn];10 int len,ans;11 char s[mxn];12 set
           
            t;13 int cmp(int a,int b){14 return (a-p[a])<(b-p[b]);15 }16 void manacher(){17 int id=0,mx=0;18 for(int i=1;i<=len;i++){19 if(mx>=i)p[i]=min(p[id]+id-i,p[2*id-i]);20 else p[i]=0;21 while(s[i+1+p[i]]==s[i-p[i]])p[i]++;22 //字符串长度是偶数，对称轴在i和i+1之间，23 //那么左边是i-p[i]，右边对称位置是i+1+p[i] 24 if(p[i]+i>mx)mx=p[i]+i,id=i;25 }26 return;27 }28 int main(){29 scanf("%d %s",&len,s+1);30 s[0]='$';31 int i,j;32 manacher();33 for(i=1;i<=len;i++)q[i]=i;34 sort(q+1,q+len+1,cmp);35 int now=1;36 for(i=1;i<=len;i++){37 while(now<=len && q[now]-p[q[now]]<=i){38 t.insert(q[now]);39 now++;40 }41 set
            
             ::iterator tmp=t.upper_bound(i+p[i]/2);42 if(tmp!=t.begin())ans=max(ans,(*--tmp-i)*4);43 }44 printf("%d\n",ans);45 return 0;46 }