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<bits/stdc++.h>

using namespace std;

#define N 500010

char 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<n;i++){

        if(pos>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<len;i++){

        s[++n]='#';

        s[++n]=t[i];

    }

    s[++n]='#';

    s[++n]='?';

    Manacher();

    int ans=0;

    for(int i=0;i<n;++i)g[i]=p[2*i+1]/2;

    for(int i=0;i<n;++i)

        for(int j=g[i]/2;j&&j*4>ans;j--)

            if(g[i+j]>=j&&g[i-j]>=j)ans=max(ans,4*j);

    printf("%d",ans);

    return 0;

}