BZOJ2342 Shoi2011 双倍回文

---

Description

Input

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

Output

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

Sample Input

16

ggabaabaabaaball

Sample Output

12

HINT

N<=500000

---

Manacher板子处理出来p数组后转化成原来串中的g数组（缩小数据规模），然后对于每个中心节点t如果两边是相等的回文串，长度为4*r，则节点t，t-j，t+j的g值都需要大于等于r，枚举所有可能的半径长度比较得到答案

---

#include
    
     using namespace std;#define N 500010char t[N],s[N<<1];int n=0,len;int p[N<<1],g[N<<1];void Manacher(){    int pos=0,x=0,id=0;    for(int i=1;i
     
      i)x=min(p[id*2-i],pos-i+1);        else x=0;        while(s[i-x]==s[i+x])x++;        x--;        if(i+x>pos)pos=i+x,id=i;        p[i]=x;    }}int main(){    scanf("%d%s",&len,t);    s[0]='!';    for(int i=0;i
      
       ans;j--)            if(g[i+j]>=j&&g[i-j]>=j)ans=max(ans,4*j);    printf("%d",ans);    return 0;}