Manacher演算法詳解

一、簡介

Manacher演算法是用來解決「最長迴文子串」的問題，它是一個時間複雜度為O(n)的演算法，比起暴力方法O(n^3)和動態規劃O(n^2)更為高效。本文將從演算法思路、代碼實現等多個方面詳細介紹Manacher演算法。

二、演算法思路

Manacher演算法的核心思想是利用已經得到的迴文中心的信息來推斷出更多的迴文中心，從而得到最長迴文子串的長度。每個迴文中心都可以向兩邊擴展，擴展出來的字元串如果仍然是迴文的，就可以得到新的迴文中心。

可以分為以下兩個步驟：

第一步：處理字元串

為了將奇數長度迴文和偶數長度迴文都統一處理，需要在每兩個字元之間插入一個符號，例如「aa」插入符號後為「#a#a#」，”123″插入符號後為「#1#2#3#」。這樣字元串的長度就變成了奇數。

第二步：計算最長迴文長度

需要維護兩個變數mx和id，其中mx表示當前在所有已經發現的迴文串中，向右端點最遠的那個迴文串的右端點的位置，id表示該迴文串的中心位置。最長迴文長度即為mx減去id。

為什麼要用mx和id？因為可以通過已經處理好的迴文串來推斷新的迴文串，這樣可以避免重複計算已經處理過的迴文串。

如何推斷新的迴文串？在已知最右邊的迴文中心的情況下，依次向右遍歷每個字元，並以該字元為中心向兩邊擴展，得到以該字元為中心的最長迴文半徑。

可能有人會問，最長迴文子串的具體值是多少呢？本演算法並沒有直接計算迴文子串的值，只是記錄了最長迴文子串的長度。如果需要得到具體的迴文子串，可以通過最長迴文子串的起點（mx-id）和長度（mx-id）計算得到。

三、代碼實現

string manacher(string s) {
    string t = "$#";
    for (int i = 0; i < s.size(); i++) {
        t += s[i];
        t += "#";
    }
    vector<int> p(t.size(), 0);
    int id = 0, mx = 0; // id是最長迴文串的中心，mx是最右邊的，迴文串能夠觸及到的最右邊的位置
    int maxLen = 0, center = 0; // maxLen是最長迴文長度，center是最長迴文中心

    for (int i = 1; i  i) {
            p[i] = min(mx - i, p[2 * id - i]);
        } else {
            p[i] = 1;
        }
        while (t[i - p[i]] == t[i + p[i]]) {
            p[i]++;
        }
        if (mx < i + p[i]) {
            id = i;
            mx = i + p[i];
        }
        if (maxLen < p[i] - 1) { // 減去插入的#字元
            maxLen = p[i] - 1;
            center = i;
        }
    }

    return s.substr((center - maxLen) / 2, maxLen);
}

四、複雜度分析

Manacher演算法的時間複雜度為O(n)，其中n為字元串長度。具體分析如下：

第一步處理字元串的時間複雜度為O(n)，因為需要插入2n+1個字元。

第二步計算最長迴文長度的時間複雜度為O(n)，因為需要遍歷2n+1個字元並計算每個字元的迴文半徑。

所以總時間複雜度為O(n)。

五、優化

Manacher演算法有一些優化的細節，這裡列舉一下：

1、對字元串進行預處理

在字元串的開頭增加一個特殊字元，這樣就不需要在處理迴文中心的時候特判邊界情況了。同時，在每個字元之間插入一個符號（例如「#」），可以避免奇偶問題，使處理過程更為簡單。

2、使用數組p在計算迴文半徑時，儘可能復用已經得到的迴文信息

如果p[j]表示以j為中心的迴文串的長度，而i的位置在[j-p[j], j+p[j]]之間，那麼如果p[2 * j – i] >= p[j]，那麼p[i]的初始值可以直接取p[2 * j – i]的值，這樣就不用從頭開始匹配了。

3、使用mx和id避免了重複計算的情況

mx表示當前在所有已經發現的迴文串中，向右端點最遠的那個迴文串的右端點的位置，而id表示該迴文串的中心位置。如果右邊的迴文串沒有超過之前計算過的迴文串右邊界，就可以避免重複計算了。

六、總結

Manacher演算法是一種高效的求解最長迴文子串的方法，時間複雜度為O(n)。通過預處理字元串、復用已有迴文信息以及使用mx和id等細節上的優化，可以進一步提高演算法的效率。