Manacher 算法学习笔记 - Baoshuo's OI Blog

Manacher 算法可以以 $O(n)$ 的时间复杂度求出一个字符串以每个位置为中心的最长回文子串。

#Manacher 算法

#预处理

对于一个字符串，它的回文子串的长度有两种主要情况：长度为奇数、长度为偶数。在本文中只需要考虑长度为奇数的字符串即可，因为可以通过插入无关字符的方式将任意长度的字符串转化为长度为奇数的字符串。例如，对于字符串 abccba，可以将其转化为 ^#a#b#c#c#b#a#$，其中 ^ 和 $ 代表字符串的起始和结束。

这样处理之后，原串中长度为奇数和偶数的回文串的长度均变为奇数，且原串中回文串的长度为新串回文串半径减一。

#流程

设 $p_i$ 表示以 $s_i$ 为中心的最大回文串的半径。再设 $\mathit{mid}$ 表示当前已找到的回文串中向右延伸最远的中心位置， $r$ 表示其右端点的下一个位置（开区间方便计算）。

当枚举到第 $i$ 个字符时，设 $j$ 为 $i$ 关于 $\mathit{mid}$ 的对称点（即 $j = 2 \times \mathit{mid} - i$ ），有两种情况：

$r < i$ ，即向右延伸最远的回文子串（黑色）没有覆盖 $i$ ，此时只有 $p_i \geq 1$ 。
$r \geq i$ 且 $r - i \geq p_j$ ，即向右延伸最远的回文子串（黑色）覆盖了 $i$ ，此时讨论关于以 $j$ 为中心的最长回文子串与以 $i$ 为中心的最长回文子串的关系，又有两种情况：
1. 以 $j$ 为中心的最长回文子串完全与以 $i$ 为中心的最长回文子串对称（蓝色），此时一定有 $p_i = p_j$ ，即 $p_i \geq p_j$ 。
2. 向右延伸的最远回文子串（黑色）没有覆盖以 $j$ 为中心的最长回文子串的对称位置串，所以 $p_i$ 只能取被覆盖的一部分（黄色），即 $p_i \geq r - i$ 。

不可以利用对称性时直接暴力扩张即可。

#代码

C++

#include <iostream>
#include <string>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = 1e7 + 5;

int p[N << 1], mid, r, ans;
std::string s1, s2;

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> s1;

    // 使字符串的长度变为 (2n + 1)，方便处理
    s2.push_back('^');
    for (const char &c : s1) {
        s2.push_back('#');
        s2.push_back(c);
    }
    s2 += "#$";

    for (int i = 1; i < s2.size(); i++) {
        // r 代表以 mid 为中心的最长回文子串的右边界
        p[i] = i < r
                 // mid * 2 - i 为 i 关于 mid 的对称点
                 ? std::min(p[mid * 2 - i], r - i)
                 // 超过边界就不是回文串了
                 : 1;

        // 暴力扩展回文串长度
        while (s2[i - p[i]] == s2[i + p[i]]) p[i]++;

        // 扩展右边界
        if (r < i + p[i]) {
            r = i + p[i];
            mid = i;
        }
    }

    for (int i = 0; i < s2.size(); i++) {
        ans = std::max(ans, p[i] - 1);  // p[i] - 1 即为以 i 为中心的最长的回文子串长度
    }

    cout << ans << endl;

    return 0;
}

#参考资料

7.1 启发式合并、Manacher 算法，AcWing 算法提高课，闫学灿，2021 年 1 月 15 日。
Manacher 学习笔记，黄浩睿，2017 年 1 月 2 日。
Manacher，OI Wiki，2021 年 8 月 11 日。