Manacher 算法

luckydrawbox · 2022-02-25 13:36:18 · 个人记录

变量

函数

char s[N],t[N];
int p[N];
int Manacher(){
    t[0]=t[1]='#';
    int len=strlen(s);
    for(int i=0;i<len;i++){
        t[i*2+2]=s[i];
        t[i*2+3]='#';
    }
    int mx=0,ans=1,id;
    len=len*2+2;
    t[len]=0;
    for(int i=1;i<len;i++){
        if(i<mx)
            p[i]=min(p[2*id-i],mx-i);
        else
            p[i]=1;
        while(t[i-p[i]]==t[i+p[i]])
            p[i]++;
        if(mx<i+p[i])
            mx=i+p[id=i];
        ans=max(ans,p[i]);
    }
    return ans-1;
}