马拉车算法

马拉车算法

char s[maxn],ss[maxn];

int p[maxn];

int len,center;

int cnt=1;

void init(){

    memset(s,0,sizeof s);

    cnt=1,s[0]='@';

    int len=strlen(ss);

    for(int i=0;i<len;i++){

        s[cnt++]='#';

        s[cnt++]=ss[i];

    }

    s[cnt++]='#';

}

void manacher(){

    p[0]=center=0;

    int maxright=0;

    for(int i=1;i<cnt;i++){

        if(i<maxright) p[i]=min(maxright-i,p[2*center-i]);

        else p[i]=1;

        while(s[i-p[i]]==s[i+p[i]]) p[i]++;

        if(p[i]+i>maxright){

            maxright=p[i]+i;

            center=i;

        }

    }

}