Manacher算法模板

namespace Manacher{
    char str[maxn<<1];
    int radius[maxn<<1];
    int len;
    void bindString(char *s,int lenS){
        for(RG i=0;i<lenS;++i){
            str[i<<1]='#';
            str[i<<1|1]=s[i];
            radius[i<<1]=radius[i<<1|1]=0;
        }
        str[lenS<<1]='#';radius[lenS<<1]=0;
        len=lenS<<1|1;
    }
    int manacher(char *s,int lenS){
        bindString(s,lenS);//处理字符串
        int R=-1,C=-1;//R-最右回文右边界 C-最右回文右边界R的对称中心
        int Res=0;
        for(RG i=0;i<len;++i){
            radius[i]=(R>i)?min(radius[(C<<1)-i],R-i+1):1;
            while(i+radius[i]<len && i-radius[i]>=0){
                if(str[i-radius[i]]==str[i+radius[i]]) ++radius[i];
                else break;
            }
            if(i+radius[i]>R){R=i+radius[i]-1;C=i;}
            Res=max(Res,radius[i]-1);
        }
        return Res;//最长回文子串的长度
    }
};