詳解Manacher算法

一、基本介紹

Manacher算法，又稱為馬拉車算法（Manacher’s Algorithm），是一種用於在字符串中查找最長迴文子串的算法，時間複雜度為O(n)。該算法的核心思想是基於已知的迴文子串來擴展新的迴文子串。

二、算法思想

Manacher算法的核心思想是基於已知的對稱中心擴展迴文子串。我們會對每個字符進行處理，以該字符為中心，分為兩種情況：

1、如果這個字符在之前的某一個迴文子串中（不一定是最長的），則我們可以利用這個已知信息，將這個字符作為以當前字符為中心的迴文子串的起點。

2、如果這個字符沒有出現在之前的任何迴文子串中，那麼我們需要拓展以這個字符為中心的迴文子串的長度。在這個過程中，我們需要判斷以當前字符為中心的迴文子串的長度，並記錄下來以備後用。

三、核心代碼

以下是Manacher算法的核心代碼，代碼中使用兩個數組記錄當前已知的最長迴文半徑和對應的迴文串。

string manacher(string& s) {
    string t = "$#";
    for (auto& c : s) {
        t += c;
        t += '#';
    }
    int n = t.size();
    vector p(n);
    int mx = 0, id = 0, resLen = 0, resCenter = 0;
    for (int i = 1; i  i ? min(p[2 * id - i], mx - i) : 1;
        while (t[i + p[i]] == t[i - p[i]]) ++p[i];
        if (mx < i + p[i]) {
            mx = i + p[i];
            id = i;
        }
        if (resLen < p[i]) {
            resLen = p[i];
            resCenter = i;
        }
    }
    return s.substr((resCenter - resLen) / 2, resLen - 1);
}

四、優化 – Manacher算法優化

在實際應用中，可以通過預處理的方式，優化Manacher算法，可以大大降低計算量，加快計算速度。

具體優化方法是先將字符串預處理，將相鄰的相同字符進行壓縮，避免重複計算。此外，通過添加虛擬字符，避免中心是一個字符時需要特殊處理的情況。

string manacher(string& s) {
    int n = s.size();
    string t;
    t += '#';
    for (int i = 0; i < n; i++) {
        t += s[i];
        t += '#';
    }
    n = t.size();

    vector p(n);

    int mx = 0, id = 0, resLen = 0, resCenter = 0;
    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 (i + p[i] > mx) {
            mx = i + p[i];
            id = i;
        }

        if (p[i] > resLen) {
            resLen = p[i];
            resCenter = i;
        }
    }

    return s.substr((resCenter - resLen) / 2, resLen - 1);
}

五、實際應用

Manacher算法可以解決多種應用問題，例如迴文字符串匹配、最長迴文子序列、最長迴文子串等等。此外，Manacher算法還可以用於字符串壓縮，比如將重複的段落（如HTML中的）進行壓縮，縮短文本長度。

六、總結

Manacher算法是一種高效的查找最長迴文子串的算法，時間複雜度為O(n)。通過預處理和優化，可以進一步提高計算效率。Manacher算法在實際應用中非常廣泛，可以解決迴文字符串匹配、最長迴文子序列、最長迴文子串等問題。