最長回文子串 —— Manacher (馬拉車) 算法

最長回文子串

回文串就是原串和反轉字元串相同的字元串。比如

aba

，

acca

。前一個是奇數長度的回文串，後一個是偶數長度的回文串。

最長回文子串就是一個字元串的所有子串中，是回文串且長度最長的子串。

Brute Force 做法

枚舉所有子串，判斷是否是回文串，然後尋找最大長度。尋找所有子串要兩重循環，判斷是否是回文要一重循環，總體時間複雜度 \(O(n^3)\)。

稍微優化一下，可以枚舉對稱中心，然後向兩邊擴充，直到遇到兩個不同的字元，枚舉下一個對稱中心，尋找其中的最大長度，時間複雜度 \(O(n^2)\)。

還可以使用 DP 解決，求原串與反轉字元串的最長公共子序列 (LCS)，時間複雜度 \(O(n^2)\)。

Manacher 算法

接下來就是重點了，Manacher 算法，在1975年由一個叫 Manacher 的人發明的。能夠在 \(O(n)\) 的時間求得最長回文子串。

前面提到，回文串有奇數長度的和偶數長度的，分類讨論有些複雜，可以參考這裡。為了避免分類讨論，可以使用一個技巧：在字元串首尾以及每兩個字元之間插入一個

'#'

。比如

abaacca

，轉換後就是

#a#b#a#a#c#c#a#

。那麼不管是奇回文

aba

還是偶回文

acca

，轉換後都是奇回文 (

#a#b#a#

和

#a#c#c#a#

)。

string init(string s) {
    string res;
    res += '@';  // 在開頭加入哨兵防止越界
    for(int i = 0; i < s.size(); ++i) {
        res += '#';
        res += s[i];
    }
    res += '#';
    res += '$';  // 結尾同樣加入哨兵防止越界
    return res;
}

Manacher 算法的思想來自于上述枚舉對稱中心的思想。該算法需要維護一個 \(len\) 數組，\(len[i]\) 代表 \(i\) 為中心的最長回文子串的長度。

設 \(s\) 為原字元串，\(mx\) 為之前計算的回文串中右端點的最大值，這個回文串的中心位置為 \(id\)，也就是 \(mx = id + len[id]\)。

每次計算的時候，\(id\) 的右邊和左邊是對稱的，是以計算右邊的時候不需要用從對稱中心向兩邊擴充的思想，而是隻用一行代碼解決：

len[i] = min(mx - i, len[2 * id - i]);

，這也是 Manacher 中最關鍵的一行代碼。

如下圖所示，\(id\) 右邊到 \(mx\) 之間的子串與 \(id\) 左邊是對稱的，是以右邊的 \(len[i]\) 最大長度為左邊與之對稱的 \(len[2\times id - i]\)，由于右邊的回文串不能超過 \(mx\) (原因見第 2 張圖)，是以

len[i] = min(mx - i, len[2 * id - i]);

。

\(id\) 右邊的回文串長度不能超過 \(mx - i\) 的原因是，如果 \(len[2 * id - i]\) 更長，如下圖的黃色部分，那麼右邊的黃色部分與左邊的黃色部分相同，那麼黑色部分應該可以更長，産生沖突。

了解了上面的内容基本上就了解了 Manacher 算法了。

代碼如下：

int Manacher(string s) {
    memset(len, 0, sizeof(len));
    int mx = 0, id = 0;
    int ans = 0;
    for(int i = 1; i < s.size() - 1; ++i) {
        if(mx > i) {
            len[i] = min(mx - i, len[2 * id - i]);  // 上面提到的最關鍵的一行代碼
        } else {
            len[i] = 1;  // 如果 i 超過右邊界要從頭計算
        }
        while(s[i - len[i]] == s[i + len[i]]) {  // 從頭計算的方法，就是上面提到的從中心向兩邊擴充
            ++len[i];
        }
        // 更新 mx 和 id
        if(i + len[i] > mx) {
            mx = i + len[i]; 
            id = i;
        }
        ans = max(ans, len[i]);
    }
    return ans - 1; // len[i] 中的最大值-1 即為原串的最長回文子串長度 
}

模闆題：HDU 3068 最長回文

題目連結：HDU 3068 最長回文

#include <bits/stdc++.h>
using namespace std;
const int maxn = 220000;

string init(string s) {
    string res;
    res += '@';
    for(int i = 0; i < s.size(); ++i) {
        res += '#';
        res += s[i];
    }
    res += '#';
    res += '$';
    return res;
}

int len[maxn];

int Manacher(string s) {
    memset(len, 0, sizeof(len));
    int mx = 0, id = 0;
    int ans = 0;
    for(int i = 1; i < s.size() - 1; ++i) {
        if(mx > i) {
            len[i] = min(mx - i, len[2 * id - i]);
        } else {
            len[i] = 1;
        }
        while(s[i - len[i]] == s[i + len[i]]) {
            ++len[i];
        }
        if(i + len[i] > mx) {
            mx = i + len[i];
            id = i;
        }
        ans = max(ans, len[i]);
    }
    return ans - 1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    string s;
    while (cin >> s) {
        string tmp = init(s);
        cout << Manacher(tmp) << endl;
    }
    return 0;
}

參考

Manacher算法圖解

Manacher算法

最長回文子串 —— Manacher (馬拉車) 算法