Manacher 备忘录

2022-03-22

一直记不住的 马拉车 板子. 前几天校内选拔赛还不会写, 惨遭吊打.

综述

对于一个长度为 $n$ 的字符串, Manacher 可以在 $O(n)$ 的时间内对每个位置 $i$ 计算一个类似于最长回文半径的东西.

具体而言, Manacher 在扫描每个位置的时候, 维护一个右端点最靠右的回文串的左右端点, 并借助于这个回文串来计算需要的信息.

回文性质的描述

记 $d_1(i)$ 表示以位置 $i$ 为中心的长度为奇数的回文串个数, 那么以 $i$ 为中心的最长回文串长度即 $2d_1(i) - 1$.

记 $d_2(i)$ 表示, 以位置 $i$ 和 $i-1$ 为中心的长度为偶数的回文串个数, 同样可以得到以 $i$ 和 $i-1$ 为中心的最长回文串长度为 $2d_2(i)$. 容易发现 $d_2(1)$ 是没有意义的.

$d_1$ 与 $d_2$ 的计算

首先来考虑 $d_1$. 对于一个长度为 $n$ 的字符串 $s$, 枚举每个位置 $i$, 并维护右端点最靠右的回文串的左右端点 $l$ 和 $r$.

优先考虑 $i < r$ 的情况. 此时对于一个位置 $i$, 可以在维护的这个回文串中得到一个对称的位置 $x$, 对于正整数 $k$, 如果 $s_{x-k}$ 到 $s_{x+k}$ 是回文串, 那么 $s_{i-k}$ 到 $s_{i+k}$ 同样是回文串.

由此可以得到

容易发现 $x$ 就是 $l + r - i$. 随后需要继续暴力维护 $d_1(i)$ 以保证其正确性.

对于 $i \geq r$ 的情况, 上面的讨论显然是不能沿用的, 暴力计算就好了. 

1
2
3
4
5
6
7
8
for (int l = 1, r = 0, i = 1; i <= n; ++i) {
  int k = (i > r)? 1: min(r - i, d1[l + r - i]);
  while (i - k >= 1 && i + k <= n && s[i - k] == s[i + k])
    ++k;
  d1[i] = k--;
  if (i + k > r)
    l = i - k, r = i + k;
}

$d_2$ 的情况类似, 此处直接给出代码实现

1
2
3
4
5
6
7
8
for (int l = 1, r = 0, i = 1; i <= n; ++i) {
  int k = (i > r)? 0: min(r - i + 1, d2[l + r - i + 1]);
  while (i - k - 1 >= 1 && i + k <= n && s[i - k - 1] == s[i + k])
    ++k;
  d2[i] = k--;
  if (i + k > r)
    l = i - k - 1, r = i + k;
}

时间复杂度

考虑 Manacher 维护的右端点 $r$ 在整个过程中单调不减, 而每次大力计算 $d$ 的过程至少令 $r$ 后移一位, 可以感性认识到时间复杂度为 $O(n)$.

偶数长度的简化处理

如果在字符串的每个字符之间都插入一个相同的特殊字符, 就可以把 $d_2$ 的计算转化为 $d_1$ 的情况. 具体而言, 对原来的字符串做这样的变换 abbaab --> #a#b#b#a#a#b#. 此外, 为了简化边界的情况, 往往在前面增加一个更特殊的字符, 即 abbaab --> $#a#b#b#a#a#b#.

之前一直是这样写 Manacher 的, 优点是实现起来简单, 不过常数也大一点.

例题

Luogu P3805 【模板】manacher 算法

题目链接

解题思路

作为 Manacher 的模板题, 自然是不会用 Manacher 写的 (

首先是经典的求一个字符串中最长回文子串长度, 此时可以对字符串正反做两次哈希然后二分, 时间复杂度 $O(n\log n)$.

在忘记 Manacher 怎么写的时候很实用.

事实上存在时间复杂度为 $O(n)$ 的做法, 不过没有单纯用二分直接. 大体上是对每个位置 $i$, 维护位置 $i$ 结尾的最长回文串长度 $R(i)$. 同时 $R(i)$ 存在性质 $R(i)\le R(i - 1) + 2$. 借助与这个性质, 暴力计算 $R(i)$ 的时间复杂度就可以做到 $O(n)$.

详见 https://oi-wiki.org/string/hash/#_4.

不过这道题有点卡常, 我写的双模数哈希的 $O(n)$ 做法 TLE 了, 换成自然溢出就过了, 但显然后者是不可取的 (

Luogu P4555 [国家集训队]最长双回文串

题目链接

解题思路

在最开始的时候提到了一点, Manacher 维护了一个右端点最靠右的回文串.

记 $f(i)$ 表示以位置 $i$ 结尾的最大回文串长度, $g(i)$ 表示以位置 $i$ 开头的最大回文串长度, 那么所求即

$f(i)$ 和 $g(i)$ 可以借助 $d_1$, $d_2$ 计算出来. 时间复杂度 $O(n)$.

代码实现

听说”随手开一大块数组就像随地大小便”, 不管了 (

> 点击显示 / 隐藏 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
// Luogu P4555
// DeP
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN = 1e5 + 5;

int n;
char str[MAXN];

int f[MAXN], g[MAXN], d1[MAXN], d2[MAXN];

int main(void) {
  scanf("%s", str + 1);

  n = strlen(str + 1);
  for (int l = 1, r = 0, i = 1; i <= n; ++i) {
    int k = (i > r)? 1: min(r - i, d1[l + r - i]);
    while (i - k >= 1 && i + k <= n && str[i + k] == str[i - k])
      ++k;
    d1[i] = k--;
    if (i + k > r)
      l = i - k, r = i + k;
  }
  for (int l = 1, r = 0, i = 1; i <= n; ++i) {
    int k = (i > r)? 0: min(r - i + 1, d2[l + r - i + 1]);
    while (i - k - 1 >= 1 && i + k <= n && str[i - 1 - k] == str[i + k])
      ++k;
    d2[i] = k--;
    if (i + k > r)
      l = i - k - 1, r = i + k;
  }
  for (int i = 1; i <= n; ++i) {
    if (i + d1[i] - 1 <= n)
      f[i + d1[i] - 1] = max(f[i + d1[i] - 1], 2 * d1[i] - 1);
    if (i + d2[i] - 1 <= n)
      f[i + d2[i] - 1] = max(f[i + d2[i] - 1], 2 * d2[i]);
    if (i - d1[i] + 1 >= 1)
      g[i - d1[i] + 1] = max(g[i - d1[i] + 1], 2 * d1[i] - 1);
    if (i - d2[i] >= 1)
      g[i - d2[i]] = max(g[i - d2[i]], 2 * d2[i]);
  }
  for (int i = n - 1; i >= 1; --i)
    f[i] = max(f[i], f[i + 1] - 2);
  for (int i = 2; i <= n; ++i)
    g[i] = max(g[i], g[i - 1] - 2);

  int ans = 0;
  for (int i = 1; i <= n - 1; ++i)
    ans = max(ans, f[i] + g[i + 1]);
  printf("%d\n", ans);
  return 0;
}

后记

看完 OI-Wiki 的评论之后, 似乎 Manacher 和 Z Algorithm 有千丝万缕的联系.

事实上两者都维护了一个右端点最靠右的满足某个性质的子串, 然后利用这个子串来计算接下来一个位置对应值. Manacher 维护的是回文串, Z Algorithm 则是一个前缀.

既然新生赛出了个 Z Algorithm, CCCC 校内选拔出了个 Manacher, 那么以后会不会继续出字符串板子呢

参考资料

© 2019-2023 DepletedPrism's Blog - Powered by Hexo - Theme Chan