马拉车板子

马拉车模板.因为不是很重要.加上原理经常忘记.这里贴一下,以备不时之需.

void Manacher(char *s,int len){

    int l=0;

    Ma[l++]='$';

    Ma[l++]='#';

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

        Ma[l++]=s[i];

        Ma[l++]='#';

    }

    Ma[l]=0;

    int mx=0,id=0;

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

        Mp[i]=mx>i ? min(Mp[2*id-i],mx-i) : 1;

        while (Ma[i+Mp[i]] == Ma[i-Mp[i]]) Mp[i]++;

        if (i+Mp[i] > mx) {

            mx=i+Mp[i];

            id=i;

        }

    }

}