Manacher算法:基于对称性的优化

  |  

摘要: 最长回文子串的 Manacher 算法

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings


本文我们看一个解决最长回文子串的专门算法:Manacher 算法。Glenn K. Manacher在1975年提出。

此前我们解决过最长回文子串的问题,一个是通过中心扩散法,在 $O(N^{2})$ 的时间复杂度解决,参考文章 中心扩散法,另一个是值域二分+字符串哈希,在 $O(N\log N)$ 解决,参考文章 用字符串哈希解决经典问题:最长重复子串、最长公共子串、最长回文子串。而 Manacher 可以在 $O(N)$ 的时间复杂度解决。

学习本算法重点体会在实际问题中如何通过对称性的信息对算法进行优化。

5. 最长回文子串

给你一个字符串 s,找到 s 中最长的回文子串。

如果字符串的反序与原始字符串相同,则该字符串称为回文字符串。

示例 1:
输入:s = “babad”
输出:”bab”
解释:”aba” 同样是符合题意的答案。

示例 2:
输入:s = “cbbd”
输出:”bb”

提示:

1
2
1 <= s.length <= 1000
s 仅由数字和英文字母组成

Manacher 算法

由于回文的长度可能是奇数也可能是偶数。为了统一处理,在所有字符之间插入一个特殊字符。记原串为 $S$,添加特殊字符后的字符串为 $T$。

定义 $p[i]$ 表示以 $T[i]$ 为中心的最长回文子串的半径。这样 $p[i] - 1$ 即对应了 $S$ 中的一个回文子串的长度。于是 Manacher 算法的关键就是维护 $p[i]$。

在枚举 $i$,维护 $p[i]$ 的过程中,我们同时维护两个变量 $c$ 和 $r$,其中:

  • $c$ 表示枚举到 $i$ 时,当前已知的回文子串中,右边界最大的回文子串的中心;
  • $r = c + p[c]$,也就是该回文子串的右边界 + 1。

当枚举到 $i$ 时,我们要算 $p[i]$,也就是以 $T[i]$ 为中心的回文串的半径是多少,按照中心扩散法的思路,向两个方向扩展对比即可。但这里利用回文子串 $T[2c-r..r]$ 的对称性,将不必要的扩展对比省去。记 $j = 2c - i$,则 $j$ 和 $i$ 以 $c$ 为中心对称,分以下情况讨论:

(1) 如果 $r - i > p[j]$,此时以 $j$ 为中心的回文串包含在以 $c$ 为中心的回文串中。由于 $i$ 和 $j$ 对称,因此以 $i$ 为中心的回文子串也包含在以 $c$ 为中心的回文串中,如下图:

此时 $p[i] \geq p[j]$。

(2) 如果 $p[j] \geq r - i > 0$,以 $j$ 为中心的回文子串不一定包含在以 $c$ 为中心的回文子串中。

由于 $T[2c-r..r]$ 是回文子串,因此 $T[i..r]$ 以及 $T[2c-r..j]$ 是对称的,以 $i$ 为中心的回文子串,向右至少会扩张到 $r$ 右边,但 $r$ 之后的部分是否对称,需要后续的匹配过程才知道。

此时 $p[i] \geq r - i$。

综合上述 (1)(2),当 $i < r$ 时,由回文串 $T[2c-r..r]$ 的对称性信息,$p[i]$ 可以不经过扩展对比直接置为 $\min(p[j], r-i)$,后续 $p[i]$ 是否可以更大,就需要扩展对比了。

(3) 如果 $r\leq i$,则关于 $p[i]$ 的对称性信息不足,只能从 $p[i]=1$ 开始扩展对比。


预处理完 $p$ 之后,即可通过 $p$ 找到所需的回文信息。比如当 $l = p[i]$ 取到了 $p$ 的最大值。则原串 $s$ 的最长回文子串长度为 $l - 1$,起始位置为 $\frac{i - l}{2}$。

时间复杂度

由于每个 p[i] 只会扩展对比一次,因此计算以 $i$ 为中心的最长回文子串的扩展对比次数摊销 $O(1)$,所以总时间复杂度为 $O(n)$。


代码 (C++,模板)

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
class Solution {
public:
string longestPalindrome(string s) {
int n = s.size();
if(n == 0 || n == 1)
return s;
// n >= 2
string t(n * 2 + 1, '#');

for(int i = 0; i < n; ++i)
t[2 * i + 1] = s[i];

int m = t.size();
vector<int> p(m, 1);
int r = 0, c = 0;
for(int i = 0; i < m; ++i)
{
int j = c * 2 - i;
// 将不用扩展对比的部分直接置进 p[i] 中
if(r > i)
{
p[i] = min(p[j], r - i);
}
while(i - p[i] >= 0 && i + p[i] < m && t[i - p[i]] == t[i + p[i]])
p[i]++;
if(i + p[i] > r)
{
r = i + p[i];
c = i;
}
}

int max_len = 0;
int max_center = -1;
int max_start = -1;
for(int i = 0; i < m; ++i)
{
if(p[i] - 1 > max_len)
{
max_len = p[i] - 1;
max_center = i;
max_start = (max_center - max_len) / 2;
}
}

return s.substr(max_start, max_len);
}
};

Share