Manacher

Manacher

本文转载自: 链接

问题定义

最长回文子串问题:给定一个字符串,求它的最长回文子串长度。

如果一个字符串正着读和反着读是一样的,那它就是回文串。下面是一些回文串的实例:

1
12321 a aba abba aaaa tattarrattat(牛津英语词典中最长的回文单词)

Brute-force 解法

对于最长回文子串问题,最简单粗暴的办法是:找到字符串的所有子串,遍历每一个子串以验证它们是否为回文串。一个子串由子串的起点和终点确定,因此对于一个长度为 n 的字符串,共有$n^2$个子串。这些子串的平均长度大约是$n/2$,因此这个解法的时间复杂度是$O(n^3)$。

改进的方法

显然所有的回文串都是对称的。长度为奇数回文串以最中间字符的位置为对称轴左右对称,而长度为偶数的回文串的对称轴在中间两个字符之间的空隙。可否利用这种对称性来提高算法效率呢?答案是肯定的。我们知道整个字符串中的所有字符,以及字符间的空隙,都可能是某个回文子串的对称轴位置。可以遍历这些位置,在每个位置上同时向左和向右扩展,直到左右两边的字符不同,或者达到边界。对于一个长度为 n 的字符串,这样的位置一共有 2n-1 个,在每个位置上平均大约要进行$n/4$次字符比较,于是此算法的时间复杂度是$O(n^2)$。

Manacher 算法

对于一个比较长的字符串,$O(n^2)$的时间复杂度是难以接受的。Can we do better?

先来看看解法 2 存在的缺陷。

1.由于回文串长度的奇偶性造成了不同性质的对称轴位置,解法 2 要对两种情况分别处理;

2.很多子串被重复多次访问,造成较差的时间效率。

缺陷 2)可以通过这个直观的小 🌰 体现:

1
2
char: a b a b a
i : 0 1 2 3 4

当 i==1,和 i ==2 时,左边的子串 aba 分别被遍历了一次。

如果我们能改善解法 2 的不足,就很有希望能提高算法的效率。Manacher 正是针对这些问题改进算法。

解决长度奇偶性带来的对称轴位置问题

Manacher 算法首先对字符串做一个预处理,在所有的空隙位置(包括首尾)插入同样的符号,要求这个符号是不会在原串中出现的。这样会使得所有的串都是奇数长度的。以插入#号为例:

1
2
aba  ———>  #a#b#a#
abba ———> #a#b#b#a#

插入的是同样的符号,且符号不存在于原串,因此子串的回文性不受影响,原来是回文的串,插完之后还是回文的,原来不是回文的,依然不会是回文。

解决重复访问的问题

我们把一个回文串中最左或最右位置的字符与其对称轴的距离称为回文半径。Manacher 定义了一个回文半径数组 RL,用 RL[i]表示以第 i 个字符为对称轴的回文串的回文半径。我们一般对字符串从左往右处理,因此这里定义 RL[i]为第 i 个字符为对称轴的回文串的最右一个字符与字符 i 的距离。对于上面插入分隔符之后的两个串,可以得到 RL 数组:

1
2
3
4
5
6
7
8
9
char:    # a # b # a #
RL : 1 2 1 4 1 2 1
RL-1: 0 1 0 3 0 1 0
i : 0 1 2 3 4 5 6

char: # a # b # b # a #
RL : 1 2 1 2 5 2 1 2 1
RL-1: 0 1 0 1 4 1 0 1 0
i : 0 1 2 3 4 5 6 7 8

上面我们还求了一下 RL[i]-1。通过观察可以发现,RL[i]-1 的值,正是在原本那个没有插入过分隔符的串中,以位置 i 为对称轴的最长回文串的长度。那么只要我们求出了 RL 数组,就能得到最长回文子串的长度。

于是问题变成了,怎样高效地求的 RL 数组。基本思路是利用回文串的对称性,扩展回文串。

我们再引入一个辅助变量 MaxRight,表示当前访问到的所有回文子串,所能触及的最右一个字符的位置。另外还要记录下 MaxRight 对应的回文串的对称轴所在的位置,记为 pos,它们的位置关系如下。

我们从左往右地访问字符串来求 RL,假设当前访问到的位置为 i,即要求 RL[i],在对应上图,i 必然是在 po 右边的(obviously)。但我们更关注的是,i 是在 MaxRight 的左边还是右边。我们分情况来讨论。

1)当 i 在 MaxRight 的左边

情况 1)可以用下图来刻画:

我们知道,图中两个红色块之间(包括红色块)的串是回文的;并且以 i 为对称轴的回文串,是与红色块间的回文串有所重叠的。我们找到 i 关于 pos 的对称位置 j,这个 j 对应的 RL[j]我们是已经算过的。根据回文串的对称性,以 i 为对称轴的回文串和以 j 为对称轴的回文串,有一部分是相同的。这里又有两种细分的情况。

以 j 为对称轴的回文串比较短,短到像下图这样。

这时我们知道 RL[i]至少不会小于 RL[j],并且已经知道了部分的以 i 为中心的回文串,于是可以令 RL[i]=RL[j]。但是以 i 为对称轴的回文串可能实际上更长,因此我们试着以 i 为对称轴,继续往左右两边扩展,直到左右两边字符不同,或者到达边界。

以 j 为对称轴的回文串很长,这么长:

这时,我们只能确定,两条蓝线之间的部分(即不超过 MaxRight 的部分)是回文的,于是从这个长度开始,尝试以 i 为中心向左右两边扩展,,直到左右两边字符不同,或者到达边界。

不论以上哪种情况,之后都要尝试更新 MaxRight 和 pos,因为有可能得到更大的 MaxRight。

具体操作如下:

step 1: 令 RL[i]=min(RL[2*pos-i], MaxRight-i)
step 2: 以 i 为中心扩展回文串,直到左右两边字符不同,或者到达边界。
step 3: 更新 MaxRight 和 pos
2)当 i 在 MaxRight 的右边

遇到这种情况,说明以 i 为对称轴的回文串还没有任何一个部分被访问过,于是只能从 i 的左右两边开始尝试扩展了,当左右两边字符不同,或者到达字符串边界时停止。然后更新 MaxRight 和 pos。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
const int maxn = 1e6+5;
char Ma[maxn*2]; //插入新字符后的字符串
int Mp[maxn*2]; //以当前位置为对称轴的回文半径

void Manacher(string &s){
int l = 0;
Ma[l++] = '$'; //防止越界
Ma[l++] = '#';
for(int i=0;i<s.size();i++){
Ma[l++] = s[i];
Ma[l++] = '#';
}
Ma[l] = 0; //结尾设置为空字符,防止越界
int mx = 1,id = 1;
for(int i=1;i<l;i++){
Mp[i] = mx > i ? min(Mp[2*id-i],mx-i) : 1;
while(Ma[i+Mp[i]] == Ma[i-Mp[i]]) Mp[i] ++; //扩展
if(i + Mp[i] > mx){
mx = i + Mp[i];
id = i;
}
}
}