BZOJ 2342: [Shoi2011]双倍回文-白红宇

BZOJ 2342: [Shoi2011]双倍回文

阅读量：4460 次

发布时间：2019-06-08

本文共 1122 字，大约阅读时间需要 3 分钟。

2342: [Shoi2011]双倍回文

Time Limit: 10 Sec Memory Limit: 128 MB

Submit: 3286 Solved: 1247

[][][]

Description

Input

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

Output

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

Sample Input

ggabaabaabaaball

Sample Output

HINT

N<=500000

题解：

Manacher+枚举

代码：

#include
      
       #include
       
        #include
        
         #define maxn 500009using namespace std;char s[maxn*2],str[maxn*2];int Len[maxn*2],len,n;void getstr(){    int k=0;str[k++]='$';    for(int i=0;i
         
          i)Len[i]=min(Len[2*id-i],mx-i);        else Len[i]=1;        while(str[i+Len[i]]==str[i-Len[i]])         Len[i]++;        if(Len[i]+i>mx)mx=Len[i]+i,id=i;    }}int main(){    scanf("%d",&n);    scanf("%s",&s);len=n;    Manacher();int ans=0;    for(int i=1;i<=len;i++){        if(str[i]=='#'&&Len[i]>ans+1)         for(int j=((Len[i]-1)/4)*2;j>ans/2;j-=2){             if(Len[i+j]>=j&&Len[i-j]>=j){                 ans=max(ans,j*2);break;             }         }    }    printf("%d\n",ans);    return 0;}