最長迴文子字串（Longest Palindromic Substring, LPS）

給一個字串 ，求 中最長的為迴文的子字串長度。

Manacher's Algorithm

為了方便，接下來的索引值都是從 0 開始，也就是說， 的第一個字元是 。

首先，先求出以每個字元為中心點的最長迴文長度，但偶數長度的迴文沒有中心點，所以這邊做一個操作：在每個字元中間和 兩端加上一個 中沒有的字元 ，結果會是：。

這個加工過的字串為 ，長度是 ，可以用一個簡單的方式來得到 ： 接下來的程式碼會用 為 . 作為範例。

1

#define T(x) ((x) % 2 ? s[(x) / 2] : '.')

接下來，我們用 來表示以 為中心點的最長迴文半徑（含中心點）。再來的重點是要如何快速求出 ，先從 的左邊讀到右邊，並且一邊計算 為何。

令 為目前為止，我們找到的迴文子字串的最右邊的結尾，也就是：，而 為這個結尾在最右邊的迴文子字串的中心點，也就是：。

先寫一個 function 來方便等等的計算， 表示從 往左和 往右的最長對稱字串長度，也就是說：令 ，，且 盡可能地大。

1
2
3
4
5

int ex(int l, int r){
    int i = 0;
    while(l - i >= 0 && r + i < n && T(l - i) == T(r + i)) i++;
    return i;
}

如果我們已經算好了前 項，現在要算第 項，我們會遇到幾種狀況：

• 沒有被任何中心點在前面的迴文覆蓋（）
  在這樣的情況下，我們不能用先前算好的東西來得到 ，所以只能硬算：

  1 2 3

  r[i] = ex(i, i); center = i; mx = i + r[i] - 1;

• 有被中心點在前面的迴文覆蓋（）
  如果這樣的話，我們可以利用覆蓋 的迴文另一邊的對稱字串來得到 。令 為迴文另一邊的對稱點，也就是說：，接著我們令 為 到這個迴文結尾的長，也就是 。再來又分成了幾種情況：
  • 以 為中心的最長迴文剛好貼齊以 為中心的迴文邊界（）
    這樣子我們只能確保 ，因為我們並不知道 是否等於 ，所以只好接著算：。
  • 以 為中心的最長迴文在 為中心的迴文範圍以內（）
    這樣我們直接確定 了，因為以 為中心的迴文兩邊是對稱的。
  • 以 為中心的最長迴文超出 為中心的迴文範圍（）
    仔細想一下會發現： 由此可知， 不會超過 ，而我們知道以 為中心的最長迴文是 ，而 也就是說，存在以 為中心，長度為 的迴文，因此，。
    

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

    int ii = center - (i - center); int len = mx - i + 1; if(i > mx){ r[i] = ex(i, i); center = i; mx = i + r[i] - 1; } else if(r[ii] == len){ r[i] = len + ex(i - len, i + len); center = i; mx = i + r[i] - 1; } else{ r[i] = min(r[ii], len); }

最後，只要算怎麼把最大的 轉成 中最大迴文子字串的長度就好了。我們知道 的每一個字元在 中，前方都會有一個字元 ，而 最後也有一個 ，剛好以 為中心的最長迴文，兩端也會是 ，所以我們可以用一樣的想法來轉回去：令以 為中心的最長迴文長度為 ，轉回去 的長度就是 （注意 必為奇數），化簡後得到 。

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
38
39
40
41
42

#define T(x) ((x) % 2 ? s[(x) / 2] : '.')

string s;
int n;

int ex(int l, int r){
    int i = 0;
    while(l - i >= 0 && r + i < n && T(l - i) == T(r + i)) i++;
    return i;
}

int main(){
    cin >> s;
    n = 2 * s.size() + 1;

    int mx = 0;
    int center = 0;
    vector<int> r(n);
    int ans = 1;
    r[0] = 1;
    for(int i = 1; i < n; i++){
        int ii = center - (i - center);
        int len = mx - i + 1;
        if(i > mx){
            r[i] = ex(i, i);
            center = i;
            mx = i + r[i] - 1;
        }
        else if(r[ii] == len){
            r[i] = len + ex(i - len, i + len);
            center = i;
            mx = i + r[i] - 1;
        }
        else{
            r[i] = min(r[ii], len);
        }
        ans = max(ans, r[i]);
    }

    cout << ans - 1 << "\n";
    return 0;
}

仔細觀察會發現，這個過程只是不斷把 往右移，因此複雜度是漂亮的 。