前言

給定一個(gè)字符串，求出其最長回文子串。例如：
s="abcd"，最長回文長度為 1；
s="ababa"，最長回文長度為 5；
s="abccb"，最長回文長度為 4，即 bccb。
以上問題的傳統(tǒng)思路大概是，遍歷每一個(gè)字符，以該字符為中心向兩邊查找。其時(shí)間復(fù)雜度為 ，效率很差。

1975 年，一個(gè)叫 Manacher 的人發(fā)明了一個(gè)算法，Manacher 算法（中文名：馬拉車算法），該算法可以把時(shí)間復(fù)雜度提升到 。下面來看看馬拉車算法是如何工作的。

傳統(tǒng)思路

i自增，從左到右，然后每個(gè)i為中心，取得最長的回文長度并記錄起止節(jié)點(diǎn)。最多要進(jìn)行兩次n的遍歷，時(shí)間復(fù)雜度為

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    if (s == null || s.length < 1) { // 傳入空直接返回''
        return '';
    }
    let start = 0;
    let end = 0;
    for (let i = 0; i < s.length; i++) {
        let len1 = expandAroundCenter(s, i, i); // 奇回文
        let len2 = expandAroundCenter(s, i, i + 1); // 偶回文
        // 分別以i為中心點(diǎn)取最長的奇偶回文長度
        let len = Math.max(len1, len2);
        if (len > (end - start)) { // 若比上一段取得回文長
            start = i - Math.floor((len - 1) / 2);
            end = i + Math.floor(len / 2);
        }
    }
    // 根據(jù)取得的最長回文左右兩個(gè)節(jié)點(diǎn)取字符串
    return s.substring(start, end + 1);
};
// 已中心擴(kuò)展判斷最長回文長度
function expandAroundCenter(s, left, right) {
    var L = left,
    R = right;
    while (L >= 0 && R < s.length && s.charAt(L) == s.charAt(R)) {
        L--;
        R++;
    }
    return R - L - 1;
}

Manacher的思路

首先因?yàn)樘幚砥婊匚暮团蓟匚臅?huì)比較繁瑣，需要分開處理。因此在首尾和各字符間插入#，將長度統(tǒng)一轉(zhuǎn)換為奇數(shù)（算法里常用的解決奇偶繁瑣問題的處理手段）
然后定義一個(gè)輔助數(shù)組p[]，其中p[i]對(duì)應(yīng)為以i為中心的最長回文長度。

輔助數(shù)組

p[i]-1就是原字符串中最長回文串的長度。
然后整個(gè)工作的重點(diǎn)就是求解p數(shù)組：

圖片.png

設(shè)置兩個(gè)變量，mx 和 id 。mx 代表以 id 為中心的最長回文的右邊界，也就是mx = id + p[id]。

假設(shè)我們現(xiàn)在求p[i]，也就是以 i 為中心的最長回文半徑，如果i < mx，如上圖，那么：
if (i < mx) p[i] = min(p[2 * id - i], mx - i);
2 * id - i為 i 關(guān)于 id 的對(duì)稱點(diǎn)，即上圖的 j 點(diǎn)，而p[j]表示以 j 為中心的最長回文半徑，因此我們可以利用p[j]來加快查找。

代碼

shutup and show me the code

#include <iostream>  
#include <cstring>
#include <algorithm>  

using namespace std;

char s[1000];
char s_new[2000];
int p[2000];

int Init()
{
    int len = strlen(s);
    s_new[0] = '$';
    s_new[1] = '#';
    int j = 2;

    for (int i = 0; i < len; i++) {
        s_new[j++] = s[i];
        s_new[j++] = '#';
    }

    s_new[j] = '\0';  // 別忘了哦
    
    return j;  // 返回 s_new 的長度
}

int Manacher()
{
    int len = Init();  // 取得新字符串長度并完成向 s_new 的轉(zhuǎn)換
    int max_len = -1;  // 最長回文長度

    int id;
    int mx = 0;

    for (int i = 1; i < len; i++) {
        if (i < mx) {
            p[i] = min(p[2 * id - i], mx - i);
            // 需搞清楚上面那張圖含義, mx 和 2*id-i 的含義
        }
        else {
            p[i] = 1;
        }
        while (s_new[i - p[i]] == s_new[i + p[i]]) {
            // 不需邊界判斷，因?yàn)樽笥?$',右有'\0'
            p[i]++;
        }
        // 我們每走一步 i，都要和 mx 比較，我們希望 mx 盡可能的遠(yuǎn)，
        // 這樣才能更有機(jī)會(huì)執(zhí)行 if (i < mx)這句代碼，從而提高效率
        if (mx < i + p[i]) {
            id = i;
            mx = i + p[i];
        }

        max_len = max(max_len, p[i] - 1);
    }

    return max_len;
}

int main() {
    while (printf("請(qǐng)輸入字符串：\n")) {
        scanf("%s", s);
        printf("最長回文長度為 %d\n\n", Manacher());
    }
    return 0;
}

直接貼代碼，核心部分就是
if (i < mx) { p[i] = min(p[2 * id - i], mx - i); }
這句公式。根據(jù)自增的i算出每個(gè)p[i]取其中的max。
整個(gè)算法中，i是自增的，每次循環(huán)要么在擴(kuò)展右邊界（代碼中的變量mx），要么直接得出結(jié)論，所以算法時(shí)間可以到O(n)。

P.S.分享一篇公眾號(hào)漫畫
這個(gè)漫畫也是逐步解釋了算法實(shí)現(xiàn)的一步步過程，比較有意思。

心得總結(jié)

首先求最長回文的方法先要掌握普通的中心擴(kuò)展探索的方法，馬拉車算法在這個(gè)前提條件下加上了右邊界的判斷，在沒有覆蓋到的時(shí)候通過中心擴(kuò)展同時(shí)更新右邊界，最后得出的p[i]數(shù)組里取出最大值即為要求的最長回文長度。

參考

Manacher 算法-劉毅