题解 P3805 【【模板】manacher算法】

zcysky · 2017-06-22 10:37:19 · 题解

这题是manacher的裸题，当然你用邻接表实现PAM（回文自动机）也是可以的。

因为PAM的复杂度也是正确的，所以造数据的时候没有卡PAM

（但是你裸的数组PAM是过不去的啦！）

manacher算法，就是在字符之间插入特殊字符避免奇偶分类讨论

然后利用之前的已有的回文信息计算回文半径。

#include<bits/stdc++.h>
#define N 31000010
using namespace std;
int n,p[N],ans;
char s[N],str[N];
void manachar(){
    int mx=0,id;
    for(int i=n;str[i]!=0;i++)str[i]=0;
    for(int i=1;i<n;i++){
        if(mx>i)p[i]=min(p[2*id-i],p[id]+id-i);
        else p[i]=1;
        for (;str[i+p[i]]==str[i-p[i]];++p[i]);
        if (p[i]+i>mx){mx=p[i]+i;id=i;}
    }
}
void init(){
    str[0]='#';str[1]='#';
    for(int i=0;i<n;i++)str[(i<<1)+2]=s[i],str[(i<<1)+3]='#';
    n=(n<<1)+2;str[n]=0;
}
int main(){
    scanf("%s",s);
    n=strlen(s);init();manachar();
    ans=0;
    for(int i=0;i<n;i++)ans=max(ans,p[i]);
    printf("%d\n",ans-1);

}