马拉车，O(n)求回文串

马拉车，O（n）求回文串

对整个马拉车算法步骤做个总结：

第一步：将每个原字母用两个特殊字符包围如：

aaa --> #a#a#a#

abab -->#a#b#a#b

同时可以由这个翻倍的字符串得到一个性质：

如果在此串中，以特殊字符，如'#'为回文中心，那么在原串中回文长度就是偶数，如果是以正常字符为回文中心，那么在原串中的回文长度就是奇数

这样可以使得所有的奇数长度的回文串变成偶数长度

第二步：设置P数组P[N*3];代表S[i]的回文半径(包括自身)，并设置id为迄今为止回文半径最大的字符位置，max为id+P[id]，该回文串的右边界位置
第三步：求p数组，这里存在一个结论：

如果mx > i，那么P[i] >= min(P[2 * id - i], mx - i)。

2id-i，将其转化到x坐标上看，正好是i关于id的对称点，可以这么理解：由于mx>i，可知i-->mx是在已知范围以内的，因为以i为回文中心的回文串是与以其关于对称点j=2id-i存在长度至少为mx-i相同回文半径的。

如图：（x和y至少是同样长的，因为以j为中心的是回文串，同id同i，根据回文串性质可得）
第四步：对于p数组的认识，p数组是在原字符串翻倍后的基础上进行运算的，很显然，若p[i]=6，那么原串的回文长度(不是回文半径)是5 :设原半径为ans,回文长度为len,那么len=ans2-1;而此时半径为x=ans2,转化可得len=x-1;

这里贴上两份模板

模板1：

void init()

{

    len1=strlen(s);

    str[0]='(';

    str[1]='#';

    for(int i=0;i<len1;i++)

    {

        str[i*2+2]=s[i];

        str[i*2+3]='#';

    }

    len2=len1*2+2;

    str[len2]=')';

}

void Manacher()

{

    memset(p,0,sizeof(p));

    int id=0,mx=0;

    for(int i=1;i<len2;i++)

    {

        if(mx>i) p[i]=min(mx-i,p[2*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;

        }

    }

}

模板2：

int Init(int n)

{

    cpy[0]='(';cpy[1]='#';

    for(int i=0,j=2;i<n;j+=2,i++)

    {

        cpy[j]=a[i];

        cpy[j+1]='#';

    }

    n=n*2+3;

    cpy[n-1]=')';

    return n;

}

void Manacher(char *s,int n,int *p)

{

    for(int i=1,j=0,k;i<n;i+=k)

    {

        while(s[i-j-1]==s[i+j+1]) j++;

        p[i]=j;

        for(k=1;k<=p[i]&&p[i-k]!=p[i]-k;k++)

        {

            p[i+k]=min(p[i-k],p[i]-k);

        }

        j=max(j-k,0);

    }

}

巴特西

马拉车，O(n)求回文串

马拉车，O（n）求回文串

最新文章

热门文章