Manacher/马拉车算法

Manacher算法可做到O(n)时间求最大回文子串
例题：http://poj.org/problem?id=3974

首先我们需要知道有一种错误的暴力方式，即以当前字符为中心，左右遍历求最长回文子串，如字符串"aba",其暴力匹配结果为121，答案就为2，但是如果字符串为“abba”,其暴力结果反而为"1111"，但是我们知道正确答案应该为4，这种暴力方法对奇数个数字符串还是适用的，但对偶数字符串不对辽~。

Manacher算法就是在这种暴力的基础上进行预处理，首先它把所有字符串都转化为奇数：在任意一个点加上"#"(也可以是其他字符，但不能和原字符串内容重复)，比如"abba"转化为"#a#b#b#a"，字符串长度变为2 * n + 1。

其次我们需要知道一些概念
①回文半径p[i]：包括回文中心在内的回文子串的一半的长度，即暴力匹配中对每个字符求它的最大回文长度
②最右回文边界mx：在遍历字符串时，每个字符遍历出的最长回文子串都会有个右边界，而mx则是所有已知右边界中最靠右的位置
③回文中心id：当前mx的第一次更新时的回文中心

然后就是核心部分p[i]的求法
若i>=mx，那只能暴力匹配了
若i<mx，情况①:p[j]∈[mx,id]，由于对称，p[i] = p[j]

情况②:p[j]∉[mx,id]，我们无法得知p[i]在mx外是否也回文，此时p[i] = mx - i，然后暴力匹配剩下的

综上p[i] = min(p[j] , mx - i)
记得遍历的时候同时更改mx和id

最后上代码

char s[N];
char news[N];
int p[N];
int Manacher()
{
    news[0] = '$'; //方便处理
    news[1] = '#';
    int pos = 1;
    for (int i = 0; s[i]; ++i)
    {
        news[++pos] = s[i];
        news[++pos] = '#';
    }
    news[++pos] = '\0'; //边界

    int res = 1;
    int id, mx = 0;
    for (int i = 1; news[i]; i++)
    {
        if (i < mx)
            p[i] = min(p[2 * id - i], mx - i);
        else
            p[i] = 1;

        while (news[i - p[i]] == news[i + p[i]]) // 不需边界判断，因为左有'$',右有'\0'
            p[i]++;

        if (mx < i + p[i]) //改变id ,mx
        {
            id = i;
            mx = i + p[i];
        }
        res = max(res, p[i] - 1); //答案是s的回文长度，即news的回文半径 - 1
    }
    return res;
}