Manacher 算法学习小记

概要

一个字符串有多少个回文的字串？最多有 \(O(n^2)\) 级别个。但 Manacher 算法却可以用 \(O(n)\) 的时间复杂度解决这个问题。同时 Manacher 算法实现非常简单。

一个显而易见的结论是：如果 \(S_{1\cdots n}\) 是回文串，那么 \(S_{2\cdots n-1}\) 也是回文串。

根据这一个性质，我们可以得到 \(O(n^2)\) 的暴力的做法：

实际上，为了方便实现，可以在两个字符间和首尾插入空字符。这样所有的回文串的长度都变为奇数。下面默认使用了这种方法，所有回文串长度为奇数，下标从 \(1\) 开始。

Manacher 充分利用了回文的性质，构造出令人惊叹的巧妙做法：

不难发现， \(r\) 是不减的。而暴力算法中向两侧暴力拓展的次数不超过 \(r\) 增加的值。所以 Manacher 算法中，暴力的部分均摊是 \(O(n)\) 的。外层循环也是 \(O(n)\) ，那么总的时间复杂度就是 \(O(n)\) 的。

例

luogu4555

\(S\) 长度 \(1e5\) 我线段树一只 \(log\) T 了？这个评测机略微有点快啊……不过可以 \(O(n)\) 的……

在 Manacher 之后，可以 \(O(n)\) 预处理出对于每个位置 \(i\) 为结尾的最长回文串和以 \(i\) 为开始的最长回文串。通过加入的空字符统计答案即可。注意必须要是两个回文串，所以单一一个空字符不能算作回文。

#include <cstdio>

#include <cstring>

#include <algorithm>

const int Maxn = 100010;

const int INF = 1e9;

char Ch[Maxn << 1];

int D[Maxn << 1];

int n, Ans, L[Maxn << 1], R[Maxn << 1];

inline void Manacher();

int main() {

    scanf("%s", Ch + 1);

    n = strlen(Ch + 1);

    for (int i = n; i >= 1; --i) Ch[i << 1] = Ch[i];

    for (int i = 0; i <= n; ++i) Ch[i << 1 | 1] = '_';

    n = n << 1 | 1;

    Ch[0] = '*', Ch[n + 1] = '\0';

    Manacher();

    for (int i = 1; i <= n; ++i) {

        L[i + D[i]] = std::max(L[i + D[i]], D[i]);

        R[i - D[i]] = std::max(R[i - D[i]], D[i]);

    }

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

        if (i & 1)

            R[i] = std::max(R[i], R[i - 2] - 2);

    for (int i = n; i >= 1; --i)

        if (i & 1)

            L[i] = std::max(L[i], L[i + 2] - 2);

    Ans = 0;

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

        if (R[i] && L[i])

            Ans = std::max(Ans, R[i] + L[i]);

    printf("%d\n", Ans);

    return 0;

}

inline void Spand(int x) {

    for(; Ch[x - D[x] - 1] == Ch[x + D[x] + 1]; ++D[x]);

    return;

}

inline void Manacher() {

    int L = 0, R = 0;

    for (int i = 1; i <= n; ++i) {

        if (i > R) {

            Spand(i);

            L = i - D[i], R = i + D[i];

            continue;

        }

        int Ops = L + (R - i);

        if (i + D[Ops] >= R) {

            D[i] = R - i;

            Spand(i);

            L = i - D[i], R = i + D[i];

            continue;

        }

        D[i] = D[Ops];

    }

    return;

}