馬拉車算法（ Manacher‘s Algorithm ）是小吳最喜歡的算法之一，因為，它真的很牛逼！

馬拉車算法是用來 查找一個字符串的最長回文子串的線性方法 ，由一個叫 Manacher 的人在 1975 年發(fā)明的，這個方法的牛逼之處在于將時間復(fù)雜度提升到了線性。

事實上，馬拉車算法在思想上和 KMP 字符串匹配算法有相似之處，都避免做了很多重復(fù)的工作。

如果你覺得馬拉車算法的中文稱呼有點俗，那么 KMP算法 就是帶了一點顏色了，你總能在有關(guān)于 KMP算法介紹的文章留言區(qū)看到它的中文俗稱。

動畫：七分鐘理解什么是KMP算法

Manacher 算法本質(zhì)上還是 中心擴(kuò)散法 ，只不過它使用了類似 KMP 算法的技巧，充分挖掘了已經(jīng)進(jìn)行回文判定的子串的特點，提高算法的效率。

下面介紹 Manacher 算法的運行流程。

首先還是“中心擴(kuò)散法”的思想：回文串可分為奇數(shù)回文串和偶數(shù)回文串，它們的區(qū)別是：奇數(shù)回文串關(guān)于它的“中點”滿足“中心對稱”，偶數(shù)回文串關(guān)于它“中間的兩個點”滿足“中心對稱”。

為了避免對于回文串字符個數(shù)為奇數(shù)還是偶數(shù)的套路，首先對原始字符串進(jìn)行預(yù)處理，方法也很簡單：添加分隔符。

第 1 步：預(yù)處理

第一步是對原始字符串進(jìn)行預(yù)處理，也就是添加分隔符。

首先在字符串的首尾、相鄰的字符中插入分隔符，例如 "babad" 添加分隔符 "#" 以后得到 "#b#a#b#a#d#"。

對這一點有如下說明：

1、分隔符是一個字符，種類也只有一個，并且這個字符一定不能是原始字符串中出現(xiàn)過的字符；

2、加入了分隔符以后，使得“間隙”有了具體的位置，方便后續(xù)的討論，并且新字符串中的任意一個回文子串在原始字符串中的一定能找到唯一的一個回文子串與之對應(yīng)，因此對新字符串的回文子串的研究就能得到原始字符串的回文子串；

3、新字符串的回文子串的長度一定是奇數(shù)；

4、新字符串的回文子串一定以分隔符作為兩邊的邊界，因此分隔符起到“哨兵”的作用。

五分鐘學(xué)算法：原始字符串與新字符串的對應(yīng)關(guān)系

第 2 步：計算輔助數(shù)組 p

輔助數(shù)組 p 記錄了新字符串中以每個字符為中心的回文子串的信息。

手動的計算方法仍然是“中心擴(kuò)散法”，此時記錄以當(dāng)前字符為中心，向左右兩邊同時擴(kuò)散，記錄能夠擴(kuò)散的最大步數(shù)。

以字符串 "abbabb" 為例，說明如何手動計算得到輔助數(shù)組 p ，我們要填的就是下面這張表。

char#a#b#b#a#b#b#index0123456789101112p

第 1 行數(shù)組 char ：原始字符串加上分隔符以后的每個字符。

第 2 行數(shù)組 index ：這個數(shù)組是新字符串的索引數(shù)組，它的值是從 0 開始的索引編號。

我們首先填 p[0]。

以 char[0] = '#' 為中心，同時向左邊向右擴(kuò)散，走 1 步就碰到邊界了，因此能擴(kuò)散的步數(shù)為 0，因此 p[0] = 0；

char#a#b#b#a#b#b#index0123456789101112p0

下面填寫 p[1] 。

以 char[1] = 'a' 為中心，同時向左邊向右擴(kuò)散，走 1 步，左右都是 "#"，構(gòu)成回文子串，于是再繼續(xù)同時向左邊向右邊擴(kuò)散，左邊就碰到邊界了，最多能擴(kuò)散的步數(shù)”為1，因此 p[1] = 1；

char#a#b#b#a#b#b#index0123456789101112p01

下面填寫 p[2] 。

以 char[2] = '#' 為中心，同時向左邊向右擴(kuò)散，走 1 步，左邊是 "a"，右邊是"b"，不匹配，最多能擴(kuò)散的步數(shù)為 0，因此 p[2] = 0；

char#a#b#b#a#b#b#index0123456789101112p010

下面填寫 p[3]。

以 char[3] = 'b' 為中心，同時向左邊向右擴(kuò)散，走 1 步，左右兩邊都是 “#”，構(gòu)成回文子串，繼續(xù)同時向左邊向右擴(kuò)散，左邊是 "a"，右邊是 "b"，不匹配，最多能擴(kuò)散的步數(shù)為 1 ，因此 p[3] = 1；

char#a#b#b#a#b#b#index0123456789101112p0101

下面填寫 p[4]。

以 char[4] = '#' 為中心，同時向左邊向右擴(kuò)散，最多可以走 4 步，左邊到達(dá)左邊界，因此 p[4] = 4。

char#a#b#b#a#b#b#index0123456789101112p01014

繼續(xù)填完 p 數(shù)組剩下的部分。

分析到這里，后面的數(shù)字不難填出，最后寫成如下表格：

char#a#b#b#a#b#b#index0123456789101112p0101410501210

說明：有些資料將輔助數(shù)組 p 定義為回文半徑數(shù)組，即 p[i] 記錄了以新字符串第 i個字符為中心的回文字符串的半徑（包括第 i 個字符），與我們這里定義的輔助數(shù)組p 有一個字符的偏差，本質(zhì)上是一樣的。

下面是輔助數(shù)組 p 的結(jié)論：輔助數(shù)組 p 的最大值是 5，對應(yīng)了原字符串 "abbabb"的 “最長回文子串” ："bbabb"。這個結(jié)論具有一般性，即：

輔助數(shù)組 `p` 的最大值就是“最長回文子串”的長度

因此，我們可以在計算輔助數(shù)組 p 的過程中記錄這個最大值，并且記錄最長回文子串。

簡單說明一下這是為什么：

如果新回文子串的中心是一個字符，那么原始回文子串的中心也是一個字符，在新回文子串中，向兩邊擴(kuò)散的特點是：“先分隔符，后字符”，同樣擴(kuò)散的步數(shù)因為有分隔符 # 的作用，在新字符串中每擴(kuò)散兩步，雖然實際上只掃到一個有效字符，但是相當(dāng)于在原始字符串中相當(dāng)于計算了兩個字符。

因為最后一定以分隔符結(jié)尾，還要計算一個，正好這個就可以把原始回文子串的中心算進(jìn)去；

五分鐘學(xué)算法：理解輔助數(shù)組的數(shù)值與原始字符串回文子串的等價性-1

如果新回文子串的中心是 #，那么原始回文子串的中心就是一個“空隙”。在新回文子串中，向兩邊擴(kuò)散的特點是：“先字符，后分隔符”，擴(kuò)散的步數(shù)因為有分隔符 # 的作用，在新字符串中每擴(kuò)散兩步，雖然實際上只掃到一個有效字符，但是相當(dāng)于在原始字符串中相當(dāng)于計算了兩個字符。

因此，“輔助數(shù)組 p 的最大值就是“最長回文子串”的長度”這個結(jié)論是成立的，可以看下面的圖理解上面說的 2 點。

五分鐘學(xué)算法：理解輔助數(shù)組的數(shù)值與原始字符串回文子串的等價性-2

寫到這里，其實已經(jīng)能寫出一版代碼。（注：本文的代碼是結(jié)合了 LeetCode 第 5 題「最長回文子串」進(jìn)行講解）

參考代碼

public class Solution {

    public String longestPalindrome(String s) {
        int len = s.length();
        if (len < 2) {
            return s;
        }
        String str = addBoundaries(s, '#');
        int sLen = 2 * len + 1;
        int maxLen = 1;

        int start = 0;
        for (int i = 0; i < sLen; i++) {
            int curLen = centerSpread(str, i);
            if (curLen > maxLen) {
                maxLen = curLen;
                start = (i - maxLen) / 2;
            }
        }
        return s.substring(start, start + maxLen);
    }

    private int centerSpread(String s, int center) {
        // left = right 的時候，此時回文中心是一個空隙，回文串的長度是奇數(shù)
        // right = left + 1 的時候，此時回文中心是任意一個字符，回文串的長度是偶數(shù)
        int len = s.length();
        int i = center - 1;
        int j = center + 1;
        int step = 0;
        while (i >= 0 && j < len && s.charAt(i) == s.charAt(j)) {
            i--;
            j++;
            step++;
        }
        return step;
    }


    /**
     * 創(chuàng)建預(yù)處理字符串
     *
     * @param s      原始字符串
     * @param divide 分隔字符
     * @return 使用分隔字符處理以后得到的字符串
     */
    private String addBoundaries(String s, char divide) {
        int len = s.length();
        if (len == 0) {
            return "";
        }
        if (s.indexOf(divide) != -1) {
            throw new IllegalArgumentException("參數(shù)錯誤，您傳遞的分割字符，在輸入字符串中存在！");
        }
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < len; i++) {
            stringBuilder.Append(divide);
            stringBuilder.append(s.charAt(i));
        }
        stringBuilder.append(divide);
        return stringBuilder.toString();
    }
}

復(fù)雜度分析

時間復(fù)雜度：O(N2)，這里 N 是原始字符串的長度。新字符串的長度是 2 * N + 1，不計系數(shù)與常數(shù)項，因此時間復(fù)雜度仍為 O(N2)。
空間復(fù)雜度：O(N)。

科學(xué)家的工作

此時，計算機(jī)科學(xué)家 Manacher 出現(xiàn)了，他充分利用新字符串的回文性質(zhì)，計算輔助數(shù)組 p。

上面的代碼不太智能的地方是，對新字符串每一個位置進(jìn)行中心擴(kuò)散，會導(dǎo)致原始字符串的每一個字符被訪問多次，一個比較極端的情況就是：#a#a#a#a#a#a#a#a#。

事實上，計算機(jī)科學(xué)家 Manacher 就改進(jìn)了這種算法，使得在填寫新的輔助數(shù)組 p 的值的時候，能夠參考已經(jīng)填寫過的輔助數(shù)組 p 的值，使得新字符串每個字符只訪問了一次，整體時間復(fù)雜度由 O(N2) 改進(jìn)到 O(N)。

具體做法是：在遍歷的過程中，除了循環(huán)變量 i 以外，我們還需要記錄兩個變量，它們是 maxRight 和 center ，它們分別的含義如下：

maxRight

maxRight 表示記錄當(dāng)前向右擴(kuò)展的最遠(yuǎn)邊界，即從開始到現(xiàn)在使用“中心擴(kuò)散法”能得到的回文子串，它能延伸到的最右端的位置。

對于 maxRight 我們說明 3 點：

“向右最遠(yuǎn)”是在計算輔助數(shù)組 p 的過程中，向右邊擴(kuò)散能走的索引最大的位置，注意：得到一個 maxRight 所對應(yīng)的回文子串，并不一定是當(dāng)前得到的“最長回文子串”，很可能的一種情況是，某個回文子串可能比較短，但是它正好在整個字符串比較靠后的位置；
maxRight 的下一個位置可能是被程序看到的，停止的原因有 2 點：（1）左邊界不能擴(kuò)散，導(dǎo)致右邊界受限制也不能擴(kuò)散，maxRight 的下一個位置看不到；（2）正是因為看到了 maxRight 的下一個位置，導(dǎo)致 maxRight 不能繼續(xù)擴(kuò)散。
為什么 maxRight 很重要？因為掃描是從左向右進(jìn)行的， maxRight 能夠提供的信息最多，它是一個重要的分類討論的標(biāo)準(zhǔn)，因此我們需要一個變量記錄它。

center

center 是與 maxRight 相關(guān)的一個變量，它是上述 maxRight 的回文中心的索引值。對于 center 的說明如下：

center 的形式化定義：

說明：x + p[x] 的最大值就是我們定義的 maxRight，i 是循環(huán)變量，0<= x< i表示是在 i 之前的所有索引里得到的最大值 maxRight，它對應(yīng)的回文中心索引就是上述式子。

maxRight 與 center 的關(guān)系

maxRight 與 center 是一一對應(yīng)的關(guān)系，即一個 center 的值唯一對應(yīng)了一個maxRight 的值；因此 maxRight 與 center 必須要同時更新。

下面的討論就根據(jù)循環(huán)變量 i 與 maxRight 的關(guān)系展開討論：

情況 1：當(dāng) i >= maxRight 的時候，這就是一開始，以及剛剛把一個回文子串掃描完的情況，此時只能夠根據(jù)“中心擴(kuò)散法”一個一個掃描，逐漸擴(kuò)大 maxRight；

情況 2：當(dāng) i < maxRight 的時候，根據(jù)新字符的回文子串的性質(zhì)，循環(huán)變量關(guān)于center 對稱的那個索引（記為 mirror）的 p 值就很重要。

我們先看 mirror 的值是多少，因為 center 是中心，i 和 mirror 關(guān)于center 中心對稱，因此 (mirror + i) / 2 = center ，所以 mirror = 2 * center - i。

根據(jù) p[mirror] 的數(shù)值從小到大，具體可以分為如下 3 種情況：

情況 2（1）：p[mirror] 的數(shù)值比較小，不超過 maxRight - i。

說明：maxRight - i 的值，就是從 i 關(guān)于 center 的鏡像點開始向左走（不包括它自己），到 maxRight 關(guān)于 center 的鏡像點的步數(shù)

五分鐘學(xué)算法：Manacher 算法分類討論情況 2（1）

從圖上可以看出，由于“以 center 為中心的回文子串”的對稱性，導(dǎo)致了“以 i 為中心的回文子串”與“以 center 為中心的回文子串”也具有對稱性，“以 i 為中心的回文子串”與“以 center 為中心的回文子串”不能再擴(kuò)散了，此時，直接把數(shù)值抄過來即可，即p[i] = p[mirror]。

情況 2（2）：p[mirror] 的數(shù)值恰好等于 maxRight - i。

五分鐘學(xué)算法：Manacher 算法分類討論情況 2（2）

說明：仍然是依據(jù)“以 center 為中心的回文子串”的對稱性，導(dǎo)致了“以 i 為中心的回文子串”與“以 center 為中心的回文子串”也具有對稱性。

因為靠左邊的 f 與靠右邊的 g 的原因，導(dǎo)致“以 center 為中心的回文子串”不能繼續(xù)擴(kuò)散；
但是“以 i 為中心的回文子串” 還可以繼續(xù)擴(kuò)散。

因此，可以先把 p[mirror] 的值抄過來，然后繼續(xù)“中心擴(kuò)散法”，繼續(xù)增加maxRight。

情況 2（3）：p[mirror] 的數(shù)值大于 maxRight - i。

五分鐘學(xué)算法：Manacher 算法分類討論情況 2（3）

說明：仍然是依據(jù)“以 center 為中心的回文子串”的對稱性，導(dǎo)致了“以 i 為中心的回文子串”與“以 center 為中心的回文子串”也具有對稱性。下面證明，p[i] = maxRight - i ，證明的方法還是利用三個回文子串的對稱性。

五分鐘學(xué)算法：Manacher 算法分類討論情況 2（3）的證明

① 由于“以 center 為中心的回文子串”的對稱性，黃色箭頭對應(yīng)的字符 c 和 e 一定不相等；

② 由于“以 mirror 為中心的回文子串”的對稱性，綠色箭頭對應(yīng)的字符 c 和 c 一定相等；

③ 又由于“以 center 為中心的回文子串”的對稱性，藍(lán)色箭頭對應(yīng)的字符 c 和 c一定相等；

推出“以 i 為中心的回文子串”的對稱性，紅色箭頭對應(yīng)的字符 c 和 e 一定不相等。

因此，p[i] = maxRight - i，不可能再大。上面是因為我畫的圖，可能看的朋友會覺得理所當(dāng)然。事實上，可以使用反證法證明：

如果“以 i 為中心的回文子串” 再向兩邊擴(kuò)散的兩個字符 c 和 e 相等，就能夠推出黃色、綠色、藍(lán)色、紅色箭頭所指向的 8 個變量的值都相等，此時“以 center 為中心的回文子串” 就可以再同時向左邊和右邊擴(kuò)散 1 格，與 maxRight 的最大性矛盾。

綜合以上 3 種情況，當(dāng) i < maxRight 的時候，p[i] 可以參考 p[mirror] 的信息，以 maxRight - i 作為參考標(biāo)準(zhǔn)，p[i] 的值應(yīng)該是保守的，即二者之中較小的那個值：

p[i] = min(maxRight - i, p[mirror]);

參考代碼

public class Solution {

    public String longestPalindrome(String s) {
        // 特判
        int len = s.length();
        if (len < 2) {
            return s;
        }

        // 得到預(yù)處理字符串
        String str = addBoundaries(s, '#');
        // 新字符串的長度
        int sLen = 2 * len + 1;

        // 數(shù)組 p 記錄了掃描過的回文子串的信息
        int[] p = new int[sLen];

        // 雙指針，它們是一一對應(yīng)的，須同時更新
        int maxRight = 0;
        int center = 0;

        // 當(dāng)前遍歷的中心最大擴(kuò)散步數(shù)，其值等于原始字符串的最長回文子串的長度
        int maxLen = 1;
        // 原始字符串的最長回文子串的起始位置，與 maxLen 必須同時更新        
        int start = 0;

        for (int i = 0; i < sLen; i++) {
            if (i < maxRight) {
                int mirror = 2 * center - i;
                // 這一行代碼是 Manacher 算法的關(guān)鍵所在，要結(jié)合圖形來理解
                p[i] = Math.min(maxRight - i, p[mirror]);
            }

            // 下一次嘗試擴(kuò)散的左右起點，能擴(kuò)散的步數(shù)直接加到 p[i] 中
            int left = i - (1 + p[i]);
            int right = i + (1 + p[i]);

            // left >= 0 && right < sLen 保證不越界
            // str.charAt(left) == str.charAt(right) 表示可以擴(kuò)散 1 次
            while (left >= 0 && right < sLen && str.charAt(left) == str.charAt(right)) {
                p[i]++;
                left--;
                right++;

            }
            // 根據(jù) maxRight 的定義，它是遍歷過的 i 的 i + p[i] 的最大者
            // 如果 maxRight 的值越大，進(jìn)入上面 i < maxRight 的判斷的可能性就越大，這樣就可以重復(fù)利用之前判斷過的回文信息了
            if (i + p[i] > maxRight) {
                // maxRight 和 center 需要同時更新
                maxRight = i + p[i];
                center = i;
            }
            if (p[i] > maxLen) {
                // 記錄最長回文子串的長度和相應(yīng)它在原始字符串中的起點
                maxLen = p[i];
                start = (i - maxLen) / 2;
            }
        }
        return s.substring(start, start + maxLen);
    }


    /**
     * 創(chuàng)建預(yù)處理字符串
     *
     * @param s      原始字符串
     * @param divide 分隔字符
     * @return 使用分隔字符處理以后得到的字符串
     */
    private String addBoundaries(String s, char divide) {
        int len = s.length();
        if (len == 0) {
            return "";
        }
        if (s.indexOf(divide) != -1) {
            throw new IllegalArgumentException("參數(shù)錯誤，您傳遞的分割字符，在輸入字符串中存在！");
        }
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < len; i++) {
            stringBuilder.append(divide);
            stringBuilder.append(s.charAt(i));
        }
        stringBuilder.append(divide);
        return stringBuilder.toString();
    }
}