Manacher 算法分析与实现

Keywords: #algorithm
Table of Contents

最近刚做完 Leetcode 上的 Longest Palindromic Substring，用的是 Manacher 算法（国内俗称马拉车算法）。之前高中打 OI 时也做过同样的题目，不过当时是作为动态规划的例题来介绍的；再加上后来我没认真学 Manacher 算法，所以直到这几天才算是初步学习了该算法。

Manacher 算法是一种能以 O(n) 的时间复杂度找出一个字符串里的所有回文子串的算法。相比于暴力搜索（O(n^3)）与动态规划/中心扩展（O(n^2)），它的时间复杂度要低得多。这篇博客就简单记录一下我对 Manacher 算法的理解。

字符串预处理

Manacher 算法运用巧妙的预处理规避了奇数长度回文子串与偶数长度回文子串的问题。预处理的方式就是在字符串的头尾和任意两个字符的中间插入占位符 #，例如将 abaaba 转化为 #a#b#a#a#b#a# —— 这样一来，原本的偶数长度回文子串就变成了以 # 为中心的奇数长度回文子串。且不论原来是奇数长度回文子串还是偶数长度回文子串，原回文子串长度 len 与新回文子串长度 len' 满足关系 len' = 2 * len + 1。

还有一项预处理并非必要的，但却值得推荐 —— 在 # 预处理后的字符串的头尾再插入 ^ 与 $ 占位符。这两个占位符不能相等，不能再原字符串中出现过：这样就能有效地减少使用 if 表达式进行边界检查的次数。为什么需要边界检查？因为 Manacher 算法的原理和中心扩展很相似，只不过充分利用了一些已知信息来减少计算。若使用中心扩展法，对于字符串 #a#b#a#b#a#，我们从最中间的 a 开始向两边扩展，直到碰到不相等的字符或字符串的头和尾扩展结束，得到一个回文子串。在头尾加上了 ^$ 占位符后我们就不需要再特意进行边界检查了，因为 ^ != $ 会自动让扩展结束。

总而言之，对于原串 abaaba，其预处理结果是 ^#a#b#a#a#b#a#$。

理解 LPS 数组

假设原字符串为 str，预处理后的字符串为 str'，那么我们需要构造一个与 str' 等长的 lps 数组，其中 lps[i] 代表以 str'[i] 为中心的最长回文子串的半径。例如对于 ^#a#b#a#a#b#a#$（abaaba），我们有：

^#a#b#a#a#b#a#$
001030161030100

不难发现 LPS 数组具有这样几个性质：

  1. 回文子串对应的 LPS 数组基本上也是回文对称的；
  2. lps[i] 和原字符串中对应的回文子串的长度相等。例如对于 str'[4] = 'b', lps[4] = 3 对应原字符中的回文子串 str[0:3] = "aba"，对于 str[7] = '#', lps[7] = 6 对应原字符中的回文子串 str[0:6] = "abaaba"；
  3. 字符 str'[i] 对应 str[(i - 1) / 2] 的字符，例如 str'[2] = 'a' 对应原字符串中下标为 (2 - 1) / 2 = 0 的字符 str[0] = 'a'。

其中性质 1 是理解 Manacher 算法的关键。

我们之前提到过中心扩展方法：在这种朴素的方法中，我们以每个字符为中心向两侧扩展，看看最长能扩展出多长的回文子串 —— 这种算法的时间复杂度是 O(n^2)。这种算法是正确的，但还可以继续优化：一是奇数长度回文子串与偶数长度回文子串的问题（我们通过字符串预处理解决了这个问题），二是我们没有充分利用已知的信息。

根据性质 2，我们要解决的问题是“找出最长回文子串”，换言之就是找出 LPS 数组中的最大值。而在计算 LPS 数组时，我们不需要每次都进行中心扩展，而可以充分利用性质 1：例如如果我们已知 lps[2] 与 lps[4]，那么利用 str[0:3] = "aba" 的回文性质，我们就能直接得出 lps[6] = lps[2]，而不需要重新中心扩展进行计算。这里我们有两个已知信息：mirror = 2 与 center = 4，而在求解 i = 6 的 LPS 值时我们就可以充分利用 lps[i] = lps[2 * center - i] = lps[mirror] 来减少计算。

通常来说我们会从左往右（从 1 到 str.length）地计算 LPS 数组，而为了最大限度地利用已知信息，center 通常时已知最靠右的回文子串，也就是说 center + lps[center] 是已知中最大的。

不过我们在性质 1 中使用了“基本上”这个词，因为这种对称性并不总是成立的；使得这种对称性不成立的情况有两种：左贴界与右越界。

处理特殊情况

左贴界

考虑这样一个字符串 str = "^#a#b#a#b#a#$"。如果我们此时已知 center = 4, str[center] = 'b'，而要求 i = 6, str[i] = 'a' 。此时如果你使用上述公式 lps[i] = lps[2 * center - i] = lps[mirror] = lps[2] = 1 就会发现我们得到的并非正确答案 —— 准确来说比正确答案更小（肉眼观察不难发现 lps[i] 应该等于 5）。

这种情况发生的原因是 str[mirror] 在扩展时碰到了原字符串的左边界，而 str[i] 则不受到此边界的限制，它可以继续扩展。在这种情况下，我们就不得不再做一些中心扩展，它的代码大概是这样的：

while (str[i + lps[i] + 1] == str[i - lps[i] - 1])
  lps[i]++;

右越界

对于 str = "^ababc$"（出于可读性考量，此处省略了部分预处理，因为不存在偶数长度回文子串），如果我们已知 center= 3, str[center] = 'a'，正在计算 i = 4, str[i] = 'b' 的 LPS 值，我们可以看到 0 = lps[i] != lps[2 * center - i] = lps[mirror] = lps[2] = 1。这是因为 i + lps[mirror] = 5 > 4 = center + lps[center]，我们越过了已知最靠右的回文子串的右边界 —— 一旦越过该边界，我们就无法确定 LPS 的回文对称性质是否依然成立。

解决方法也很简单，我们让 lps[i] = min(center + lps[center] - i, lps[mirror])。需要注意的是，右越界以后事实上并不需要、也不能继续（像左贴界一样）中心扩展，尽管我们具体代码实现时并不特别区分左贴界与右越界的情况。这是因为（反证法）如果能继续扩展，那么 lps[center] 就应该比现在的更大。

无已知信息

即使 Manacher 算法利用已知信息减少了计算量，我们终归还是要做一些中心扩展计算的。比如（如果我们从左往右计算）我们在计算 lps[1] 时就不会有任何已知信息；如果 i > center + lps[center] —— 这意味着我们正在计算的位置已经超过了已知最靠右的回文子串的右边界，我们同样也没有已知信息可利用。

这时候我们应该假设 lps[i] = 0，然后再进行中心扩展。

实现 Manacher 算法

接下来我们就使用 C++ 实现马拉车算法，来找出最长回文子串。

string manacher(string &str) {
  int center{0}, max{0}, right{0}, lps[str.size()]{-1, 0};
  for (auto i{1}; i < str.size() - 1; lps[++i] = 0) {
    if (i < right)
      lps[i] = min(right - i, lps[2 * center - i]);
    while (str[i + lps[i] + 1] == str[i - lps[i] - 1])
      lps[i]++;
    if (i + lps[i] > right)
      center = i, right = i + lps[i];
    if (lps[i] > lps[max])
      max = i;
  }
  return vector<int>{(max - lps[max] - 1) / 2, lps[max]};
}

此函数接收一个已经预处理过 的字符串，返回一个二元数组作为 std::string::substr 的参数。其中 max 是最长回文子串再预处理后的字符串中的中心坐标，根据性质 3 可知 (max - lps[max] - 1) / 2 是原字符串中最长回文子串的起始下标，根据性质 2 可知 lps[max] 就是原字符串中最长回文子串的长度。

参考文献：

← prev next →