Manacher算法的裸题

下面简单说一下复杂度为O(n)的马拉车算法
首先过程中涉及到的变量有:
p[i]表示以t[i]字符为中心的回文子串的半径
id为最大回文子串中心的位置
mx是回文串能延伸到的最右端的位置

通过p数组我们就可以找到最长回文子串及其位置,,那么下面我们就来看如何求p数组
这里有一个非常神奇的东西

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

慢慢理解它……
这一行代码相当于
如果mx > i, 则 p[i] = min(p[2 * id - i], mx - i)
否则, p[i] = 1
看图说话

第一种情况,即mx延伸到i点以外,i的对称点j就在id的回文串内,那么由于整个从mx的对称点mx是一个回文串,所以有一个非常优美的性质,就是id到mx和id到mx的对称点是完全对称的(此处手动加粗)
1.如果jmx的对称点,那么ij一样,如上图,即p【i】=p【j】;
2.如果jmx的对称点,那么只能保证i在mx前是回文的,即以i为中心,mx-i为半径以内是回文的,如下图,即p【i】=mx-i;

然后再一步步对下一位进行比较;

第二种情况,i在mx外,就只能一步步比较了;
至此,核心内容就说完了
但这还是不够的
为什么呢?
显然(真的是显然吗?)
上面的东东只能搞出回文串长度是奇数的情况,即有一个对称中心,比如aba
但回文串长度是偶数怎么办呢,比如abba
不要方
加一个预处理
在原字符串的每两个字符间插入一个“#”
实际上对于求回文串是没有影响的(非常科学)
为了防止越界,还要在最前面加一个其他神奇的字符,比如“¥”
然后就是这样
bob –> ¥#b#o#b#
noon –> ¥#n#o#o#n#
这样做的好处是不论原字符串是奇数还是偶数个,处理之后得到的回文串的个长度都是奇数(虽然长得很丑)

此处应有代码
顺便%sdfzxh

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char a[300010],b[300010];
int p[300010];
int manacher()
{
    int ans=0;
    b[0]='$';
    b[1]='#';
    int len=strlen(a);
    for(int i=1;i<=len;i++)
    {
        b[2*i]=a[i-1];
        b[2*i+1]='#';
    }
    len=len*2+2;
    int mx=0,id=0;
    for(int i=1;i<len;i++)
    {
        p[i]=mx>i?min(p[2*id-i],mx-i):1;
        while(b[i+p[i]]==b[i-p[i]]) p[i]++;
        p[i]--;
        if(i+p[i]>mx)
        {
            mx=i+p[i];
            id=i;
        }
        ans=max(ans,p[i]);
    }
    return ans;
}
int main()
{
    while(scanf("%s",a)!=EOF)
    {
        printf("%d\n",manacher());
    }
    return 0;
}