字符串算法：Manacher 算法

什么是 Manacher 算法？

Manacher 算法是一种用于在 线性时间内 找到字符串中最长回文子串的算法。传统的中心扩展法时间复杂度为 O(n²)，而 Manacher 算法通过利用回文串的对称性，避免了大量重复的比较，达到了 O(n) 的效率。

核心思想

Manacher 算法的核心在于维护一个 回文半径数组 p 和两个变量：

• p[i]: 以字符 i 为中心的回文串的半径长度。
• max_right: 当前已发现的所有回文串中，右边界能到达的最远位置。
• center: 对应 max_right 的那个回文串的中心位置。

算法通过一个巧妙的技巧解决了回文串长度为奇数和偶数的不同情况：在原字符串的每个字符之间以及首尾都插入一个特殊字符（如 #），这样所有回文串的长度都变成了奇数。例如，"aba" 变成 "#a#b#a#"，"abba" 变成 "#a#b#b#a#"。

算法流程

1. 预处理字符串: 将原字符串 s 转换为带有分隔符的新字符串 t。
2. 遍历新字符���: 遍历 t 的每一个字符 i，计算其回文半径 p[i]。
   • 利用对称性: 如果当前位置 i 在 max_right 的覆盖范围内（即 i < max_right），我们可以找到 i 关于 center 的对称点 j = 2 * center - i。此时，p[i] 的值至少是 p[j]。我们可以直接利用这个已知信息：p[i] = min(p[j], max_right - i)。
   • 中心扩展: 在利用对称性得到一个初始半径后，我们再从这个半径开始，向两边进行暴力扩展，直到不再是回文为止。
   • 更新 max_right 和 center: 如果以 i 为中心的回文串的右边界 i + p[i] 超过了当前的 max_right，我们就更新 max_right 和 center。

C++ 伪代码

string preprocess(const string& s) {
    string t = "#";
    for (char c : s) {
        t += c;
        t += '#';
    }
    return t;
}

void manacher(const string& s) {
    string t = preprocess(s);
    int n = t.length();
    vector<int> p(n, 0);
    int center = 0, max_right = 0;

    for (int i = 0; i < n; ++i) {
        // 利用对称性
        if (i < max_right) {
            p[i] = min(p[2 * center - i], max_right - i);
        }

        // 中心扩展
        int left = i - (1 + p[i]);
        int right = i + (1 + p[i]);
        while (left >= 0 && right < n && t[left] == t[right]) {
            p[i]++;
            left--;
            right++;
        }

        // 更新 max_right 和 center
        if (i + p[i] > max_right) {
            max_right = i + p[i];
            center = i;
        }
    }
    // p[i] - 1 就是原字符串中的回文串长度
    // 找到 p 数组中的最大值即可得到最长回文子串
}

Manacher 算法是字符串处理中一个非常精妙的例子，它将一个看似需要平方级时间的问题，通过记录和复用已知信息，优化到了线性时间。