Manacher

发表于 分类于

本文介绍一个很特殊的字符串算法——Manacher算法，用以解决一个很特殊的问题——最长回文子串。

问题描述

最长回文子串：最长的、回文的 子串。

回文串：\(s = \text{rev}(s)\)，即 \(s[i] = s[n-i-1]\) 。

暴力枚举

暴力枚举所有子串，然后判断是否回文，复杂度 \(O(N^3)\) 。

枚举对称轴

考虑到回文的性质，每个回文串被对称轴唯一确定，所以可以枚举对称轴，然后向两端拓展，复杂度 \(O(N^2)\) 。

简单的预处理

因为回文串有 奇数 和 偶数 两种情况，处理起来比较麻烦，如果能够统一处理就好了。

我们可以使用一种填充技术，在头尾以及每个字符中间插入一个字符集外的字符，比如 '#' ，这样一来，整个字符串的长度变成 \(2N+1\)，一定为奇数，我们只需要求得这个新字符串的最长回文子串，然后将结果除以 \(2\) 即可。

Manacher

暴力枚举对称轴为什么慢？因为当对称轴向右移动一位，我们需要重新从零开始一步步的尝试向两端拓展。显然将我们之前的结果都抛弃了，能否利用起来之前的结果就是关键。

设 \(d[i]\) 表示以 \(i\) 为对称轴的半径，下表为例：

0 1 2 3 4 5
s a b c b c b
d 1 1 2 3 2 1

我们需要维护一个区间 \([L, R]\) ，表示之前所有的回文串中 最靠右 的那个。通过这个 \([L, R]\)，我们可以快速的计算出 \(d[i]\) ：

  • \(i > R\)， 之前的记录没有参考意义，直接从 \(i\) 开始尝试向两端拓展；
  • \(i \leq R\)，我们知道 \([L, R]\) 是一个回文串，所以 \(i\) 的对称位置 \(j = L + R - i\)，利用 \(d[j]\) 来更新 \(d[i]\):
    • 如果 \(j - d[j] + 1 \geq L\)，说明以 \(j\) 为中心的回文串完全包含在 \([L, R]\) 中，那么显然 \(d[i]\) 至少可以等于 \(d[j]\)；
    • 如果 \(j - d[j] + 1 < L\)，换言之 \(i + d[j] - 1 > R\)，因为我们对于 \(R\) 后面一无所知，所以 \(d[i]\) 只能从 \(R - i + 1\) 开始；
    • 无论是上述哪种情况，继续暴力地尝试增长 \(d[i]\)。
    • 不要忘记动态地更新 \([L, R]\)。

时间复杂度比较容易分析，因为 \(R\) 是单调增加的，所以算法复杂度是 \(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
int manacher(const string & s) {
    string t = "#";
    for (auto c : s) {
        t.push_back(c);
        t.push_back('#');
    }
    
    int n = t.length();
    vector<int> d(n);

    int L = 0, R = -1;
    for (int i = 0; i < n; ++i) {
        int k = i > R ? 1 : min(d[L+R-i], R-i+1);
        while (0 <= i-k && i+k < n && t[i-k] == t[i+k]) ++k;
        d[i] = k;
        if (R < i + k - 1) {
            L = i - k + 1;
            R = i + k - 1;
        }
    }
    
    return *max_element(d.begin(), d.end()) - 1;
}