马拉车算法 ( Manacher’s Algorithm ) 理解与实现

这里介绍用于计算回文子串的算法 Manacher’s Algorithm。

简单的办法

容易想到复杂度为 $O(n^2)$ 的算法，对于每一个字符及他们的间隔进行遍历，每个位置从中心扩展，即每次同时检查关于该点轴对称的两点，如果相等继续扩展直至无法扩展，例如对于串 “abacaba” 需要遍历下面的所有位置 ( 间隔处使用 “#” 标出，实现时，也可以先在字符串间加入 “#” 号，这样就不用考虑字符间隔的情况 )：

1	# a # b # a # c # a # a # a #

对于每个位置都进行扩展，例如对下面的 b 进行扩展：

1 2	# a # b # a # c # a # a # a # \|

得到 ( 数字代表第几次扩展 )

1 2	# a # b # a # c # a # a # a # 4 3 2 1 2 3 4

b 向左右扩展为 “#a#b#a#”，无法继续扩展，去掉辅助的 #, 以此点为中心的回文串最大长度为 3。

在比如扩展下面的间隔：

1 2	# a # b # a # c # a # a # a # \|

得到：

1 2	# a # b # a # c # a # a # a # 3 2 1 2 3

扩展结果为 “#a#a#”，去掉 # 得到 aa 以此点为中心的回文串最长为 2

对于每个点都做这样的扩展即可得到最大回文串长度。

马拉车算法原理

马拉车算法利用回文串的对称性减少字符的访问次数，使复杂度降为 $O(n)$ 。

考虑我们从左到右计算每个点的最大回文串长度，这里考虑字符串 “abacabac”, 先做间隔扩展得到：

1	# a # b # a # c # a # b # a # c #

我们假设在 c 点 (第一个) 及 c 点以前的部分已经计算，于是已知 ( 数字代表得到的结果，这里暂时把 # 也算上 )：

1 2	# a # b # a # c # a # b # a # c # 1 3 1 7 1 3 1 15

对于 c 接下来的 #，在他计算时，可以知道，他被包括在 c 为中心的回文串中，这意味着，# 的回文串长度至少有其关于 c 的对称点的长度那么长：

1
2
3

# a # b # a # c # a # b # a # c #
            x'| x
            1   >=1

当然这里也扩展不了了，所以直接的到结果为 1，同样的方法我们可以继续计算直到 b 之前：

1 2	# a # b # a # c # a # b # a # c # 1 3 1 7 1 3 1 15 1 3 1

对于 b 首先，由于它还在第一个 c 的回文串范围内，所以根据对称性，可以知道：

1
2
3

# a # b # a #  c # a # b # a # c #
      x'       |       x
1 3 1 7 1 3 1 15 1 3 1 >=7

所以这个 b 的回文串至少有 7 这么长，所以我们直接从长度 7 开始继续遍历 ( “|” 表示一直的部分，这部分跳过，从 x 处开始)：

1 2	# a # b # a # c # a # b # a # c # x \| \| \| \| \| \| \| x

最终得到的串为 “#c#a#b#a#c#”，长度为 ( 包括 # ) 11。

以上例子说明马拉车算法的基本原理，基本流程和简单的方法类似，但是在从左向右计算的过程中，利用已经计算的回文串的对称性，使得后续计算回文串时可以跳过一些判断来降低复杂度

马拉车算法实现

这部分基于之前描述的原理说明，下面先说明算法中的一些设定：

算法使用 P 存储每个点的结果，这个结果是每个点的扩展长度，例如 “#a#”, a 向左右扩展了 1 次，所以 P = 1, 这个值正是去掉 # 后的结果字符串长度，即最终的结果。
如何确定每个 i 计算时用来找对称点的中心 ( 例如前面的 c )？每次计算完后，需要把中心更新为覆盖范围离右边缘最近的那个。

下面是参考 Manacher’s Algorithm Explained— Longest Palindromic Substring 实现的 js 版本算法：

function LPS(str) {
  // 这里扩展间隔
  const nstr = '#' + str.split('').join('#') + '#';
  // 使用 P 存结果
  const sz = nstr.length, P = Array(sz).fill(0);
  // c: 参考中心，r：中心覆盖到的最右边的点，max：存储最大长度。
  let c = 0, r = 0, max = 0;
  for (let i = 0; i < sz; i++) {
    // 计算镜像点
    const mirror = (2 * c) - i;

    // 如果 i 在参考中心的范围内，把 P 值直接扩展，这步是重点
    if (i < r) {
      P[i] = Math.min(P[mirror], r - i);
    }

    // 从已经扩展的结果之后接着尝试扩展
    let a = i + (1 + P[i]), b = i - (1 + P[i]);
    while (a < sz && b >= 0 && nstr[a] == nstr[b]) {
      P[i]++;
      a++;
      b--;
    }

    // 如果新的结果的边缘更靠近有边缘，那就更新中心各新的右边缘。
    if (i + P[i] > r) {
      c = i;
      r = i + P[i];
      // 更新返回值
      if (P[i] > max) {
        max = P[i];
      }
    }
  }
  return max;
}

参考资料

Manacher’s Algorithm Explained— Longest Palindromic Substring
Manacher’s Algorithm – Linear Time Longest Palindromic Substring – Part 2

马拉车算法 ( Manacher’s Algorithm ) 理解与实现

算法学习笔记

简单的办法

马拉车算法原理

马拉车算法实现

参考资料

FEATURED TAGS

FRIENDS