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

tags: Competitive Programming Note

本文已停止更新，新版請至 WiwiHo 的競程筆記

給一個字串

$S$，求

$S$ 中最長的為迴文的子字串長度。

Manacher's Algorithm

為了方便，接下來的索引值都是從 0 開始，也就是說，

$S$ 的第一個字元是

$S_0$。

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

$S$ 兩端加上一個

$S$ 中沒有的字元

$c$，結果會是：

$c{S}_{0}c{S}_{1}c{S}_{2}c{S}_3...S_{|S|-1}c$。

這個加工過的字串為

$T$，長度是

$2\times |S|+1$，可以用一個簡單的方式來得到

$T_i$：

$$T_i=\{\begin{array}{ll}{S}_{\lfloor \frac{i}{2}\rfloor }& \text{if }imod2=1\\ c& \text{else}\end{array}$$ 接下來的程式碼會用

$c$ 為 . 作為範例。

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

接下來，我們用

$R_i$ 來表示以

$T_i$ 為中心點的最長迴文半徑（含中心點）。再來的重點是要如何快速求出

$R_i$，先從

$T$ 的左邊讀到右邊，並且一邊計算

$R_i$ 為何。

令

$\text{mx}$ 為目前為止，我們找到的迴文子字串的最右邊的結尾，也就是：

$max\{i+R_i-1\}$，而

$\text{center}$ 為這個結尾在最右邊的迴文子字串的中心點，也就是：

$\text{mx}=\text{center}+R_{\text{center}}-1$。

先寫一個 function 來方便等等的計算，

$\text{ex}(l,r)$ 表示從

$l$ 往左和

$r$ 往右的最長對稱字串長度，也就是說：令

$t=\text{ex}(l,r)$，

$T_{(l-t+1)..l}=T_{r..(r+t-1)}$，且

$t$ 盡可能地大。

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;
}

如果我們已經算好了前

$i-1$ 項，現在要算第

$i$ 項，我們會遇到幾種狀況：

• $T_i$ 沒有被任何中心點在前面的迴文覆蓋（
  $i>\text{mx}$）
  在這樣的情況下，我們不能用先前算好的東西來得到
  $R_i$，所以只能硬算：
  ​​​​r[i] = ex(i, i);
  ​​​​center = i;
  ​​​​mx = i + r[i] - 1;
  

• $T_i$ 有被中心點在前面的迴文覆蓋（
  $i\le \text{mx}$）
  如果這樣的話，我們可以利用覆蓋
  $T_i$ 的迴文另一邊的對稱字串來得到
  $R_i$。令
  $i^{\prime }$ 為迴文另一邊的對稱點，也就是說：
  $i^{\prime }=\text{center}-(i-\text{center})$，接著我們令
  $\text{len}$ 為
  $T_i$ 到這個迴文結尾的長，也就是
  $\text{len}=\text{mx}-i+1$。再來又分成了幾種情況：
  • 以
    $T_{i^{\prime }}$ 為中心的最長迴文剛好貼齊以
    $T_{\text{center}}$ 為中心的迴文邊界（
    $R_{i^{\prime }}=\text{len}$）
    這樣子我們只能確保
    $R_i\ge R_{i^{\prime }}$，因為我們並不知道
    $T_i+R_{i^{\prime }}$ 是否等於
    $T_i-R_{i^{\prime }}$，所以只好接著算：
    $R_i=R_{i^{\prime }}+\text{ex}(i-R_{i^{\prime }},i+R_{i^{\prime }})$。
  • 以
    $T_{i^{\prime }}$ 為中心的最長迴文在
    $T_{\text{center}}$ 為中心的迴文範圍以內（
    $R_{i^{\prime }}<\text{len}$）
    這樣我們直接確定
    $R_i=R_{i^{\prime }}$ 了，因為以
    $T_{\text{center}}$ 為中心的迴文兩邊是對稱的。
  • 以
    $T_{i^{\prime }}$ 為中心的最長迴文超出
    $T_{\text{center}}$ 為中心的迴文範圍（
    $R_{i^{\prime }}>\text{len}$）
    仔細想一下會發現：
    $$\begin{gathered} T_{\text{center}-R_{\text{center}}}\ne T_{\text{center}+R_{\text{center}}} \\ {T}_{\text{center}-R_{\text{center}}}=T_{i^{\prime }-\text{len}}=T_{i^{\prime }+\text{len}}=T_{i-\text{len}} \\ {T}_{\text{center}+R_{\text{center}}}=T_{i+\text{len}} \\ {T}_{i-\text{len}}\ne T_{i+\text{len}} \end{gathered}$$ 由此可知，
    $R_i$ 不會超過
    $\text{len}$，而我們知道以
    $T_{i^{\prime }}$ 為中心的最長迴文是
    $R_{i^{\prime }}$，而
    $R_{i^{\prime }}>\text{len}$也就是說，存在以
    $T_i$ 為中心，長度為
    $\text{len}$ 的迴文，因此，
    $R_i=\text{len}$。
  ​​​​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);
  ​​​​}
  

最後，只要算怎麼把最大的

$R_i$ 轉成

$S$ 中最大迴文子字串的長度就好了。我們知道

$S$ 的每一個字元在

$T$ 中，前方都會有一個字元

$c$，而

$T$ 最後也有一個

$c$，剛好以

$T_i$ 為中心的最長迴文，兩端也會是

$c$，所以我們可以用一樣的想法來轉回去：令以

$T_i$ 為中心的最長迴文長度為

$t=R_i\times 2-1$，轉回去

$S$ 的長度就是

$\frac{(t-1)}{2}$（注意

$t$ 必為奇數），化簡後得到

$R_i-1$。

#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;
}

仔細觀察會發現，這個過程只是不斷把

$\text{mx}$ 往右移，因此複雜度是漂亮的

$O(|S|)$。