馬拉車演算法

發表於 分類於 閱讀次數： Waline： 文章字數： 1.8k

最近在學習馬拉車演算法，簡單記錄一下心得。（如有疏漏，請指出

先看 模板題 ，要求最長迴文串的長度。

首先思考樸素演算法，顯然是 O(n3) ，無法透過。而馬拉車演算法能將時間複雜度最佳化到 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，因為中點座標公式，得到 $\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;
}

小結

馬拉車演算法實用且容易理解，但熟練掌握還需要練習。

作業 | 最長雙迴文串