概述

Manacher算法是一种用于快速计算字符串中回文串长的算法，复杂度为O(n)。下面介绍该算法的原理及实现细节。

原理

我们从朴素地查找回文串开始，我们枚举回文串的回文中心，并向两边扩展，这种算法是O(n^2)的。我们来想一个问题，如果有串abcbaabcbaabcbaabcba，它本身是回文的，而子串abcba也是回文的，在寻找过程中，abcba可能会被多次遍历到。我们能否把已经找到过的abcba信息利用起来，优化算法呢。Manacher就实现了这种优化。
首先我们要对字符串进行一步处理，因为奇回文abcba和偶回文abba存在不同的模式，需要分别考虑，我们把字符之间都插入一个特殊字符，如#，就可以把偶回文也转化为奇回文的情况了，如abba→$#a#b#b#a#。其中，字符串0位置的字符$是用来防止越界的。
这里给一个对齐表方便观察。

我们考虑在上面的例子中，#a#b#c#b#a#a#b#c#b#a#存在子回文串#a#b#c#b#a#，在下一次遇到该回文串的回文中心时，我们可以考虑在整个大回文串找到这个中心的对称点，就像这样：

#a#b#c#b#a#a#b#c#b#a#
     ^         ^

并把对称点的答案直接拿过来用。如果我们用mx代表当前极大回文串右端点，id代表当前极大回文串中心位置，p数组代表某个位置为中心的最长回文串半径，那么代码写出来应该是这样的：

if(i < mx) p[i] = std::min(p[2 * id - i], mx - i);

然后我们再来扩展修正这个p值，动态地维护当前极大回文串即可。
在处理过的串中p数组代表的半径，而我们发现p数组的值实际上为原串中该位置为中心的最长回文串长+1，因此可以这样直接计算出答案。

实现

本代码可以通过【P3805】【模板】manacher算法 – 洛谷一题。

// Code by KSkun, 2018/6
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>

const int MAXN = 22000005;

char s1[MAXN], s2[MAXN];
int n, tot, p[MAXN], mx;

inline int manacher() {
    s2[tot++] = '$'; s2[tot++] = '#';
    for(int i = 1; i <= n; i++) {
        s2[tot++] = s1[i]; s2[tot++] = '#';
    }
    int mxlen = 0, mx = 0, id;
    for(int i = 1; i < tot; i++) {
        if(i < mx) p[i] = std::min(p[(id << 1) - i], mx - i);
        else p[i] = 1;
        while(s2[i - p[i]] == s2[i + p[i]]) p[i]++;
        if(mx < i + p[i]) {
            id = i; mx = i + p[i];
        }
        mxlen = std::max(mxlen, p[i] - 1);
    }
    return mxlen;
}

int main() {
    scanf("%s", s1 + 1); n = strlen(s1 + 1);
    printf("%d", manacher());
    return 0;
}

参考资料

• Manacher算法 – 经典算法与数据结构 – SegmentFault 思否
• 题解 P3805 【【模板】manacher算法】 – A Simple Blog – 洛谷博客