马拉车算法

发表于 分类于 阅读次数： Waline： 本文字数： 1.9k

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

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

首先思考朴素算法，显然是 O(n3)O(n^3) ，无法通过。而马拉车算法能将时间复杂度优化到 O(n)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，枚举每个对称中心，记录 l 和 r 即目前最长回文字符串的左右端点。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，因为中点坐标公式，得到 l+r2=i+j2=mid\frac{l+r}{2} = \frac{i+j}{2} = mid ，得到 j=l+r−ij = 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;
}

小结

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

作业 | 最长双回文串