马拉车算法

最近在学习马拉车算法,简单记录一下心得。(如有疏漏,请指出

先看 模板题 ,要求最长回文串的长度。

首先思考朴素算法,显然是 $O(n^3)$ ,无法通过。而马拉车算法能将时间复杂度优化到 $O(n)$。

性质

  • 对于一个回文字符串,必然有一个对称中心,在对称中心两侧的部分均全等。
  • 一个回文字符串对称之后得到的一定也是回文字符串
    即 aba x aba
    • 但是对于奇数、偶数长度的回文字符串,这个对称中心可能是字符,也可能在两个字符中间。
      如:ab | ba, a b a

所以考虑,在两个字符中间都插入隔板 #,即 abba 变成 #a#b#b#a#。原长度为 n 的字符串,增加 n+1 隔板,长度变成 2n+1 必然是奇数,方便统计。

思路

马拉车算法,即记录一直最长回文子串区间,对朴素算法进行优化。

因为是朴素算法两侧向外拓展,隔板对判断回文无影响。p[i] 数组存储以 str[i] 为对称中心的回文字符串半径长度。半径长度中计算了隔板个数,所以得到的就是回文字符串长度。

1
2
3
4
5
6
7
8
9
10
11
for(int i = 0, l = 0, r = -1;i<s2.size(); i++){
int k = (i>r)? 1 : min(p[l+r-i], r-i+1);
while(0 <= i-k && i+k<s2.size() && s2[i-k]==s2[i+k]){
k++;
}
p[i] = --k; // 注意最后一次循环会对加上一个 1
if(i+k>r){
l = i-k;
r = i+k;
}
}

先记录 i,枚举每个对称中心,记录 lr 即目前最长回文字符串的左右端点。k 则是目前半径长度。

算法主体就是朴素算法,向左右两端拓展。

考虑优化。如果i处在一个回文子串中,因为对称性,可以得到与i对称的点j的最长回文串长度。因为i不断增加,对称的点的坐标一定小于i即已经更新过。

由于上文推断的性质,回文子串可以对称得到。注意单个字符也可以考虑成一个回文子串。所以 k 可以从 之前的 p[j] 开始计算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
(设 x 表示 [l,r] 对称中心,j 就是 i 关于 x 的对称点)

1. 案例1
l r
#a#b#b#a#
^ ^ ^
j x i

2. 案例2
l r
#a#b#a#b#a#b#a#
^ ^ ^
j x i

手推方便理解

然后考虑如何计算 j,因为中点坐标公式,得到 $\frac{l+r}{2} = \frac{i+j}{2} = mid$ ,得到 $j = l+r-i$。

但是因为确定区间,且偶数情况存在。所以还应判断 j 是否在区间内。

而如果不在区间内,很显然应该从1开始枚举。

所以得到:

1
int k = (i>r)? 1 : min(p[l+r-i], r-i+1);

每次更新 l r 区间长度即可。

AC Code

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
#include <cstdio>
#include <iostream>
#include <string>

using namespace std;

int p[110000001];

int main() {
// Type your code here
string s1;
cin >> s1;
string s2;
s2.resize(s1.size()*2+4);
s2[0] = '~';
s2[1] = '#';
for(int i = 0, j=2; i<s1.size(); i++, j+=2){
s2[j] = s1[i];
s2[j+1] = '#';
}
int ans = 0;
for(int i = 0, l = 0, r = -1;i<s2.size(); i++){
int k = (i>r)? 1 : min(p[l+r-i], r-i+1);
while(0 <= i-k && i+k<s2.size() && s2[i-k]==s2[i+k]){
k++;
}
k--;
p[i] = k;
if(i+k>r){
l = i-k;
r = i+k;
}
ans = max(ans,p[i]);
}
cout << ans << endl;
return 0;
}

小结

马拉车算法实用且容易理解,但熟练掌握还需要练习。

作业 | 最长双回文串