最长回文子串 Manacher 算法

前言
¶

Manacher 算法可在线性时间内求出一个字符串中所有以任意位置或相邻两个位置为中心的最长回文串。

算法原理
¶

记给定的字符串为 $S$，其长度为 $N$。为方便描述，在 $S$ 中的任一对相邻字符间插入一个特殊字符 $，目的是保证新串中所有的回文子串长度都为奇数（只是为了方便讨论算法，实际实现时并不需要此操作）。设以 $S_i$ 为中心的最长回文串长度为 $2 r_i + 1$。取 $j < i$，作 $i$ 点关于 $j$ 的对称点 $i'$：

若 $j + r_j > i$，根据对称性，不难有 $i' > j - r_j$.
接下来观察在 $j + r_j > i$ 前提下，$r_i$ 和此前已求出的 $r_{i'}$ 及 $r_j$ 之间的关系：
- 情况一：$i' - r_{i'} > j - r_j$
  如下图所示，由对称性可以断言 $r_i = r_{i'}$。
  图1
  事实上，假设 $k' = i' - r_{i'} - 1$ 关于 $j$ 的对称点为 $k$; $k$ 关于 $i$ 的对称点为 $k_i$；$k_i$ 关于 $j$ 的对称点为 $k'_i$ 。如下图所示，显然有 $S_k = S_{k'},\; S_{k_i}=S_{k'_i}$，且 $S_{k'} \neq S_{k'_i}$；所以 $S_k \neq S_{k_i}$，故 $r_i=r_{i'}$。
  图2
- 情况二：$i' - r_{i'} < j - r_j$
  如下图所示，由对称性可以断言 $i + r_i = j + r_j$，即 $r_i = j + r_j - i$。
  图3
  首先，根据对称性，显然有 $i + r_i >= j + r_j$ 成立；其次，若 $i + r_i > j + r_j$，根据对称性则有 $S_{j+r_j + 1} = S_{j-r_j - 1}$ 成立，这和 $r_j$ 为以 $j$ 为中心的最长回文串半径相冲突；故 $i + r_i = j + r_j$。
否则，$j + r_j \leqslant i$，此时不能做出更多的假设，只能暴力匹配。幸运地是，可以证明暴力匹配的次数为总字符数，即 $O(N)$ 的。

剩下的问题是如何快速找到这样的 $j$ 呢？注意到，其实我们只要获得 $j+r_j$ 值最大的那个 $j$ 就好了，这很容易在均摊 $O(1)$ 的复杂度内做到（只要再扫描 $i$ 时顺便更新 $j$ 就好了）。

算法实现
¶

上文中提到的的插入特殊字符是为了方便讲解，实现时可以将回文串 $[l,r]$ 的长度存在 $r_{l+r}$ 中。不难发现，当回文串长度为偶数时，$l+r \equiv 1\mod 2$。

参考了《ACM国际大学生程序设计竞赛:算法与实现》的代码。高亮的那行代码展示了如何维护 $j$

C++

manacher.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void manacher(char* S, int* R, int n) {
  R[0] = 1;
  int _size = (n << 1) - 1;
  for (int i = 1, j = 0; i < _size; ++i) {
    int l = i >> 1, r = i - l;
    int rst = (j - 1 >> 1) + R[j];
    R[i] = rst < r ? 0 : min(rst - r + 1, R[(j << 1) - i]);

    while (
      l - R[i] >= 0 && 
      r + R[i] < n && 
      S[l - R[i]] == S[r + R[i]]
    ) ++R[i];
    if (r + R[i] > rst) j = i;
  }
}

Typescript （你也可以直接使用 @algorithm.ts/manacher）

manacher.ts

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function manacher(text: string): number[] {
  const N = text.length
  const _size = (N << 1) - 1 
  const R: number[] = new Array(_size)

  R[0] = 1
  for (let i = 1, j = 0; i < _size; ++i) {
    const p: number = i >> 1
    const q: number = i - p
    const r: number = ((j + 1) >> 1) + R[j] - 1

    let L = r < q ? 0 : Math.min(r - q + 1, R[(j << 1) - i])
    for (; p > L - 1 && q + L < N; ++L) {
      if (text[p - L] !== text[q + L]) break
    }
    R[i] = L

    if (q + L - 1 > r) j = i
  }
}

复杂度分析
¶

由于每一次只从未被匹配过的字符出发往右扩展，一共只有 $O(N)$ 个字符，所以复杂度是线性的。

空间复杂度 $O(N)$
时间复杂度 $O(N)$

核心代码：

core.ts

1
2
let L = r < q ? 0 : Math.min(r - q + 1, R[(j << 1) - i])
if (q + L - 1 > r) j = i

小记
¶

第一次接触这个算法是在 2016 年武大的校赛上；头一回没有抱大腿获奖; 虽然奖品有点坑。。。

《ACM国际大学生程序设计竞赛:算法与实现》清华大学出版社余勇主编
@algorithm.ts/manacher

前言¶

算法原理¶

算法实现¶

复杂度分析¶

小记¶

Related¶

前言
¶

算法原理
¶

算法实现
¶

复杂度分析
¶

小记
¶

Related
¶