Manacher算法：基于对称性的优化，信息论直觉

摘要: 最长回文子串的 Manacher 算法

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

本文我们看一个解决最长回文子串的专门算法：Manacher 算法。Glenn K. Manacher在1975年提出。

此前我们解决过最长回文子串的问题，一个是通过中心扩散法，在 $O(N^{2})$ 的时间复杂度解决，参考文章 中心扩散法，另一个是值域二分+字符串哈希，在 $O(N\log N)$ 解决，参考文章 用字符串哈希解决经典问题：最长重复子串、最长公共子串、最长回文子串。而 Manacher 可以在 $O(N)$ 的时间复杂度解决。

Manacher 算法本身的适用性比较窄，只能解决回文子串相关的问题，但它背后的思想却非常普适，也就是如何合理地应用对称性信息解决问题，而物理世界与业务场景中充满了各种对称性。学习本算法重点体会在实际问题中如何通过对称性的信息对算法进行优化。

思路的来源：对称性信息能不能用上

给定一个字符串 $s$，给定一个位置 $i$，问以 $i$ 为中心的最长回文子串，记其答案为 $p(i)$，可以从 $i$ 出发向两端进行扩散，这样可以在 $O(n)$ 的时间复杂度得到答案。

用中心扩散法求最长回文子串时，需要枚举 $s$ 的每个位置 $i=0,1,\cdots,n-1$，通过中心扩散法求出 $p(i)$，过程中记录最大值即可。

如果只是孤立地求 $p(i)$，那么只能$O(n)$地走一轮中心扩散。但在求最长回文子串的过程中，在求 $p(i)$ 时，$p(0), p(1), \cdots, p(i-1)$ 都已经求过了，那么一个很自然的问题是：在计算 $p(0), p(1), \cdots, p(i-1)$ 时所得的信息能否用上，使得我们在求 $p(i)$ 时不用那么暴力地进行中心扩散。

这一问非常符合信息论直觉：没有任何信息的时候，算 $p(i)$ 需要 $O(n)$ 中心扩散，现在有了算 $p(0),p(1),\cdots,p(i-1)$ 时的这么多已知信息，算 $p(i)$ 如果还需要 $O(n)$，就显得不合理了。所以这里是存在优化的可能性的，但给出一个具体的优化方案并不容易。

Manacher 算法利用了回文的对称性，将计算 $p(0),p(1),\cdots,p(i-1)$ 时的信息成功利用上了，使得算 $p(i)$ 时不用暴力地中心扩散了。这是一个利用对称性信息优化算法的经典例子。

5. 最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

示例 1：
输入：s = “babad”
输出：”bab”
解释：”aba” 同样是符合题意的答案。

示例 2：
输入：s = “cbbd”
输出：”bb”

提示：

1 <= s.length <= 1000
s 仅由数字和英文字母组成

Manacher 算法

由于回文的长度可能是奇数也可能是偶数。为了统一处理，在所有字符之间插入一个特殊字符。记原串为 $S$，添加特殊字符后的字符串为 $T$。

定义 $p[i]$ 表示以 $T[i]$ 为中心的最长回文子串的半径。这样 $p[i] - 1$ 即对应了 $S$ 中的一个回文子串的长度。于是 Manacher 算法的关键就是维护 $p[i]$。

在枚举 $i$，维护 $p[i]$ 的过程中，我们同时维护两个变量 $c$ 和 $r$，其中：

• $c$ 表示枚举到 $i$ 时，当前已知的回文子串中，右边界最大的回文子串的中心；
• $r = c + p[c]$，也就是该回文子串的右边界 + 1。

---

当枚举到 $i$ 时，我们要算 $p[i]$，也就是以 $T[i]$ 为中心的回文串的半径是多少，按照中心扩散法的思路，向两个方向扩展对比即可。但这里利用回文子串 $T[2c-r..r]$ 的对称性，将不必要的扩展对比省去。记 $j = 2c - i$，则 $j$ 和 $i$ 以 $c$ 为中心对称，分以下情况讨论：

(1) 如果 $r - i > p[j]$，此时以 $j$ 为中心的回文串包含在以 $c$ 为中心的回文串中。由于 $i$ 和 $j$ 对称，因此以 $i$ 为中心的回文子串也包含在以 $c$ 为中心的回文串中，如下图：

此时 $p[i] \geq p[j]$。

(2) 如果 $p[j] \geq r - i > 0$，以 $j$ 为中心的回文子串不一定包含在以 $c$ 为中心的回文子串中。

由于 $T[2c-r..r]$ 是回文子串，因此 $T[i..r]$ 以及 $T[2c-r..j]$ 是对称的，以 $i$ 为中心的回文子串，向右至少会扩张到 $r$ 右边，但 $r$ 之后的部分是否对称，需要后续的匹配过程才知道。

此时 $p[i] \geq r - i$。

综合上述 (1)(2)，当 $i < r$ 时，由回文串 $T[2c-r..r]$ 的对称性信息，$p[i]$ 可以不经过扩展对比直接置为 $\min(p[j], r-i)$，后续 $p[i]$ 是否可以更大，就需要扩展对比了。

(3) 如果 $r\leq i$，则关于 $p[i]$ 的对称性信息不足，只能从 $p[i]=1$ 开始扩展对比。

---

预处理完 $p$ 之后，即可通过 $p$ 找到所需的回文信息。比如当 $l = p[i]$ 取到了 $p$ 的最大值。则原串 $s$ 的最长回文子串长度为 $l - 1$，起始位置为 $\frac{i - l}{2}$。

时间复杂度

由于每个 p[i] 只会扩展对比一次，因此计算以 $i$ 为中心的最长回文子串的扩展对比次数摊销 $O(1)$，所以总时间复杂度为 $O(n)$。

---

代码 (C++，模板)

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        if(n == 0 || n == 1)
            return s;
        // n >= 2
        string t(n * 2 + 1, '#');

        for(int i = 0; i < n; ++i)
            t[2 * i + 1] = s[i];

        int m = t.size();
        vector<int> p(m, 1);
        int r = 0, c = 0;
        for(int i = 0; i < m; ++i)
        {
            int j = c * 2 - i;
            // 将不用扩展对比的部分直接置进 p[i] 中
            if(r > i)
            {
                p[i] = min(p[j], r - i);
            }
            while(i - p[i] >= 0 && i + p[i] < m && t[i - p[i]] == t[i + p[i]])
                p[i]++;
            if(i + p[i] > r)
            {
                r = i + p[i];
                c = i;
            }
        }

        int max_len = 0;
        int max_center = -1;
        int max_start = -1;
        for(int i = 0; i < m; ++i)
        {
            if(p[i] - 1 > max_len)
            {
                max_len = p[i] - 1;
                max_center = i;
                max_start = (max_center - max_len) / 2;
            }
        }

        return s.substr(max_start, max_len);
    }
};

---