Manacher算法

首先用一个非常巧妙的方式,将所有可能的奇数/偶数长度的回文子串都转换成了奇数长度:在每个字符的两边都插入一个特殊的符号。比如 abba 变成 #a#b#b#a#, aba变成 #a#b#a#。为了进一步减少编码的复杂度,可以在字符串的开始加入另一个特殊字符,这样就不用特殊处理越界问题,比如 $#a#b#a#。

下面以字符串 12212321 为例,经过上一步,变成了 s = $#1#2#2#1#2#3#2#1# ;
然后用一个数组 p[i] 来记录以字符 S[i] 为中心的最长回文子串向左/右扩张的长度(包括 s[i] ),比如 s[i] 和 p[i] 的对应关系:

s[i] # 1 # 2 # 2 # 1 # 2 # 3 # 2 # 1 #
p[i] 1 2 1 2 5 2 1 4 1 2 1 6 1 2 1 2 1

(从上表可以看出,p[i]-1 正好是原字符串中回文串的总长度)

那么怎么计算 p[i] 呢?该算法增加两个辅助变量 id 和 mx
id : 表示右边界最远的回文子串中心的位置 (注:貌似很多blog说 id 表示最大回文子串中心的位置,我觉得是不对的)
mx : 则为 id+p[id],也就是上述回文子串的右边界


然后可以得到一个非常神奇的结论,这个算法的关键点就在这里了:

如果 mx > i,那么 p[i] >= min(p[2 * id - i], mx - i) ,其中 i 与 j 关于 id 对称。

1
2
3
4
5
6
// 上述结论可写成如下代码:
// 记 j = 2 * id - i,也就是说 j 是 i 关于 id 的对称点。
if (mx - i > P[j])
P[i] = P[j];
else // P[j] >= mx - i
P[i] = mx - i; // P[i] >= mx - i,取最小值,之后再匹配更新。

(1) 当 mx - i > p[j] 时,

图1.  mx-i > p[i]

由 id 的定义知,红色线段的字符串是以 id 为中心的最长回文串!
同时, j 是 i 关于 id 的对称点,由于红色字符串是回文字符串,所以关于 j 对称的回文子串关于 i 对称的回文子串完全一样的!!(即图中两段绿色的线条)
而满足 mx-i>p[j] 时, 说明此时 j 的回文子串半径 小于 j 到 mx 对称的左端点的差,此时可以初始化 p[i] = p[j] 。

(2) 当 mx-i <= p[j] 时,

图2.  mx-i <= p[j]

由于 mx-i<=p[j] ,说明此时$j$的回文子串半径 大于或等于 j 到 mx 对称的左端点的差. 在目前最长回文串(即红色所示)的范围内,关于 i 对称的回文串可能的长度为 mx-i , 此时可以初始化 p[i]=mx-i . 而对于红色范围之外的(即超过mx的字符),它是否关于 i 对称呢? 因此,还需再对 p[i] 的回文子串半径进行进一步的增大!!

(3) 当 mx<=i 时,
对于 mx<=i 的情况,无法对 p[i] 做更多的假设,只能令 p[i] = 1 ,然后再去匹配了.


代码实现:

1
2
3
4
5
6
7
8
9
// 转换字符串str, 比如将字符串 123 转换成 $#1#2#3#
void Transform (char* str) {
int l = 0;
s[l++] = '$'; s[l++] = '#';
for (int i = 0; str[i]; ++i) {
s[l++] = str[i]; s[l++] = '#';
}
s[l] = 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int Manacher (char* str) {
Transform(str);
int mx = 0, id = 0, ans = 0;
memset (p, 0, sizeof(p));
for (int i = 1; s[i]; ++i) {
p[i] = mx > i ? min(p[2*id-i], mx-i) : 1; // 如上所述
while (s[i+p[i]] == s[i-p[i]]) p[i]++;
//以i为中心,p[i]为半径,查找是否还有可能构成回文的情况
if (i + p[i] > mx) { // 更新最远的右边界
mx = i+p[i];
id = i;
}
ans = max(ans, p[i]-1); // 答案即为所有的p[i]-1中的最大值
}
return ans;
}
分享到 评论