方法一：暴力匹配 （Brute Force）

暴力解法雖然時(shí)間復(fù)雜度高，但是思路清晰遵堵、編寫簡(jiǎn)單晚伙，因?yàn)榫帉懙恼_性高，完全可以使用暴力匹配算法檢驗(yàn)我們編寫的算法的正確性拷窜。

（這里就不展示暴力匹配的寫法了开皿，實(shí)際上是我很懶。）

方法二：中心擴(kuò)散法

中心擴(kuò)散法的想法很簡(jiǎn)單：遍歷每一個(gè)索引篮昧，以這個(gè)索引為中心赋荆，利用“回文串”中心對(duì)稱的特點(diǎn)，往兩邊擴(kuò)散懊昨，看最多能擴(kuò)散多遠(yuǎn)窄潭。要注意一個(gè)細(xì)節(jié)：回文串的長(zhǎng)度可能是奇數(shù)，也可能是偶數(shù)酵颁。

LeetCode 第 5 題：中心擴(kuò)散法

我們完全可以設(shè)計(jì)一個(gè)方法嫉你，兼容以上兩種情況：

1、如果傳入重合的索引編碼躏惋，進(jìn)行中心擴(kuò)散幽污，此時(shí)得到的最長(zhǎng)回文子串的長(zhǎng)度是奇數(shù)；

2簿姨、如果傳入相鄰的索引編碼距误，進(jìn)行中心擴(kuò)散，此時(shí)得到的最長(zhǎng)回文子串的長(zhǎng)度是偶數(shù)。

參考代碼 1：

具體編碼細(xì)節(jié)在以下的代碼的注釋中體現(xiàn)准潭。

class Solution:
    def longestPalindrome(self, s):
        size = len(s)
        if size == 0:
            return ''

        # 至少是 1
        longest_palindrome = 1
        longest_palindrome_str = s[0]

        for i in range(size):
            palindrome_odd, odd_len = self.__center_spread(s, size, i, i)
            palindrome_even, even_len = self.__center_spread(s, size, i, i + 1)

            # 當(dāng)前找到的最長(zhǎng)回文子串
            cur_max_sub = palindrome_odd if odd_len >= even_len else palindrome_even
            if len(cur_max_sub) > longest_palindrome:
                longest_palindrome = len(cur_max_sub)
                longest_palindrome_str = cur_max_sub

        return longest_palindrome_str

    def __center_spread(self, s, size, left, right):
        """
        left = right 的時(shí)候攘乒，此時(shí)回文中心是一條線，回文串的長(zhǎng)度是奇數(shù)
        right = left + 1 的時(shí)候惋鹅，此時(shí)回文中心是任意一個(gè)字符则酝，回文串的長(zhǎng)度是偶數(shù)
        """
        l = left
        r = right

        while l >= 0 and r < size and s[l] == s[r]:
            l -= 1
            r += 1
        return s[l + 1:r], r - l - 1

public class Solution {

    public String longestPalindrome(String s) {
        int len = s.length();
        if (len == 0) {
            return "";
        }
        int longestPalindrome = 1;
        String longestPalindromeStr = s.substring(0, 1);
        for (int i = 0; i < len; i++) {
            String palindromeOdd = centerSpread(s, len, i, i);
            String palindromeEven = centerSpread(s, len, i, i + 1);
            String maxLen = palindromeOdd.length() > palindromeEven.length() ? palindromeOdd : palindromeEven;
            if (maxLen.length() > longestPalindrome) {
                longestPalindrome = maxLen.length();
                longestPalindromeStr = maxLen;
            }
        }
        return longestPalindromeStr;
    }

    private String centerSpread(String s, int len, int left, int right) {
        int l = left;
        int r = right;
        while (l >= 0 && r < len && s.charAt(l) == s.charAt(r)) {
            l--;
            r++;
        }
        // 這里要特別小心，跳出 while 循環(huán)的時(shí)候闰集，是第 1 個(gè)滿足 s.charAt(l) != s.charAt(r) 的時(shí)候
        // 所以沽讹，不能取 l，不能取 r
        return s.substring(l + 1, r);
    }
}

復(fù)雜度分析：

• 時(shí)間復(fù)雜度：武鲁。
• 空間復(fù)雜度：爽雄。

方法三：動(dòng)態(tài)規(guī)劃（推薦）

推薦理由：暴力解法太 naive，中心擴(kuò)散不普適沐鼠，Manacher 就更不普適了挚瘟，是專門解這個(gè)問題的方法。而用動(dòng)態(tài)規(guī)劃我認(rèn)為是最有用的饲梭，可以幫助你舉一反三的方法乘盖。

補(bǔ)充說明：Manacher 算法有興趣的朋友們可以了解一下，有人就借助它的第一步字符串預(yù)處理思想憔涉，解決了 LeetCode 第 4 題订框。因此以上推薦僅代表個(gè)人觀點(diǎn)。

解決這類 “最優(yōu)子結(jié)構(gòu)” 問題兜叨，可以考慮使用 “動(dòng)態(tài)規(guī)劃”：

1穿扳、定義 “狀態(tài)”；
2国旷、找到 “狀態(tài)轉(zhuǎn)移方程”矛物。

記號(hào)說明： 下文中，使用記號(hào) s[l, r] 表示原始字符串的一個(gè)子串跪但，l履羞、r 分別是區(qū)間的左右邊界的索引值特漩，使用左閉、右閉區(qū)間表示左右邊界可以取到涂身。舉個(gè)例子，當(dāng) s = 'babad' 時(shí)蛤售，s[0, 1] = 'ba' 妒潭，s[2, 4] = 'bad'雳灾。

1、定義 “狀態(tài)”冯凹，這里 “狀態(tài)”數(shù)組是二維數(shù)組谎亩。

dp[l][r] 表示子串 s[l, r]（包括區(qū)間左右端點(diǎn)）是否構(gòu)成回文串，是一個(gè)二維布爾型數(shù)組宇姚。即如果子串 s[l, r] 是回文串匈庭，那么 dp[l][r] = true。

2浑劳、找到 “狀態(tài)轉(zhuǎn)移方程”阱持。

首先，我們很清楚一個(gè)事實(shí)：

1魔熏、當(dāng)子串只包含 個(gè)字符衷咽，它一定是回文子串；

2蒜绽、當(dāng)子串包含 2 個(gè)以上字符的時(shí)候：如果 s[l, r] 是一個(gè)回文串镶骗，例如 “abccba”，那么這個(gè)回文串兩邊各往里面收縮一個(gè)字符（如果可以的話）的子串 s[l + 1, r - 1] 也一定是回文串滓窍，即：如果 dp[l][r] == true 成立卖词，一定有 dp[l + 1][r - 1] = true 成立。

根據(jù)這一點(diǎn)吏夯，我們可以知道，給出一個(gè)子串 s[l, r] 即横，如果 s[l] != s[r]噪生，那么這個(gè)子串就一定不是回文串跺嗽。如果 s[l] == s[r] 成立桨嫁，就接著判斷 s[l + 1] 與 s[r - 1]璃吧，這很像中心擴(kuò)散法的逆方法畜挨。

事實(shí)上，當(dāng) s[l] == s[r] 成立的時(shí)候毡咏，dp[l][r] 的值由 dp[l + 1][r - l] 決定呕缭，這一點(diǎn)也不難思考：當(dāng)左右邊界字符串相等的時(shí)候修己，整個(gè)字符串是否是回文就完全由“原字符串去掉左右邊界”的子串是否回文決定箩退。但是這里還需要再多考慮一點(diǎn)點(diǎn)：“原字符串去掉左右邊界”的子串的邊界情況戴涝。

1啥刻、當(dāng)原字符串的元素個(gè)數(shù)為 個(gè)的時(shí)候，如果左右邊界相等娄涩，那么去掉它們以后蓄拣，只剩下 個(gè)字符球恤，它一定是回文串咽斧，故原字符串也一定是回文串张惹；

2岭洲、當(dāng)原字符串的元素個(gè)數(shù)為 個(gè)的時(shí)候钦椭，如果左右邊界相等，那么去掉它們以后侥锦，只剩下 個(gè)字符恭垦，顯然原字符串也一定是回文串番挺。

把上面兩點(diǎn)歸納一下玄柏，只要 s[l + 1, r - 1] 至少包含兩個(gè)元素，就有必要繼續(xù)做判斷瀑晒，否則直接根據(jù)左右邊界是否相等就能得到原字符串的回文性苔悦。而“s[l + 1, r - 1] 至少包含兩個(gè)元素”等價(jià)于 l + 1 < r - 1玖详，整理得 l - r < -2蟋座，或者 r - l > 2脚牍。

綜上莫矗，如果一個(gè)字符串的左右邊界相等作谚，以下二者之一成立即可：
1妹懒、去掉左右邊界以后的字符串不構(gòu)成區(qū)間眨唬，即“ s[l + 1, r - 1] 至少包含兩個(gè)元素”的反面，即 l - r >= -2瓦宜，或者 r - l <= 2临庇；
2假夺、去掉左右邊界以后的字符串是回文串已卷，具體說淳蔼，它的回文性決定了原字符串的回文性肖方。

于是整理成“狀態(tài)轉(zhuǎn)移方程”：

dp[l, r] = (s[l] == s[r] and (l - r >= -2 or dp[l + 1, r - 1]))

或者

dp[l, r] = (s[l] == s[r] and (r - l <= 2 or dp[l + 1, r - 1]))

編碼實(shí)現(xiàn)細(xì)節(jié)：因?yàn)橐獦?gòu)成子串 l 一定小于等于 r 俯画，我們只關(guān)心 “狀態(tài)”數(shù)組“上三角”的那部分取值艰垂。理解上面的“狀態(tài)轉(zhuǎn)移方程”中的 (r - l <= 2 or dp[l + 1, r - 1]) 這部分是關(guān)鍵猜憎，因?yàn)?or 是短路運(yùn)算，因此截亦，如果收縮以后不構(gòu)成區(qū)間崩瓤，那么就沒有必要看繼續(xù) dp[l + 1, r - 1] 的取值却桶。

讀者可以思考一下：為什么在動(dòng)態(tài)規(guī)劃的算法中颖系，不用考慮回文串長(zhǎng)度的奇偶性呢嘁扼。想一想，答案就在狀態(tài)轉(zhuǎn)移方程里面蒋院。

具體編碼細(xì)節(jié)在代碼的注釋中已經(jīng)體現(xiàn)欺旧。

參考代碼 2：

class Solution:
    def longestPalindrome(self, s: str) -> str:
        size = len(s)
        if size <= 1:
            return s
        # 二維 dp 問題
        # 狀態(tài)：dp[l,r]: s[l:r] 包括 l辞友，r 称龙，表示的字符串是不是回文串
        # 設(shè)置為 None 是為了方便調(diào)試鲫尊，看清楚代碼執(zhí)行流程
        dp = [[False for _ in range(size)] for _ in range(size)]

        longest_l = 1
        res = s[0]

        # 因?yàn)橹挥?1 個(gè)字符的情況在最開始做了判斷
        # 左邊界一定要比右邊界小疫向，因此右邊界從 1 開始
        for r in range(1, size):
            for l in range(r):
                # 狀態(tài)轉(zhuǎn)移方程：如果頭尾字符相等并且中間也是回文
                # 在頭尾字符相等的前提下搔驼，如果收縮以后不構(gòu)成區(qū)間（最多只有 1 個(gè)元素）侈询，直接返回 True 即可
                # 否則要繼續(xù)看收縮以后的區(qū)間的回文性
                # 重點(diǎn)理解 or 的短路性質(zhì)在這里的作用
                if s[l] == s[r] and (r - l <= 2 or dp[l + 1][r - 1]):
                    dp[l][r] = True
                    cur_len = r - l + 1
                    if cur_len > longest_l:
                        longest_l = cur_len
                        res = s[l:r + 1]
            # 調(diào)試語句
            # for item in dp:
            #     print(item)
            # print('---')
        return res

public class Solution {

    public String longestPalindrome(String s) {
        int len = s.length();
        if (len <= 1) {
            return s;
        }
        int longestPalindrome = 1;
        String longestPalindromeStr = s.substring(0, 1);
        boolean[][] dp = new boolean[len][len];
        // abcdedcba
        //   l   r
        // 如果 dp[l, r] = true 那么 dp[l + 1, r - 1] 也一定為 true
        // 關(guān)鍵在這里：[l + 1, r - 1] 一定至少有 2 個(gè)元素才有判斷的必要
        // 因?yàn)槿绻?[l + 1, r - 1] 只有一個(gè)元素囊嘉，不用判斷哗伯，一定是回文串
        // 如果 [l + 1, r - 1] 表示的區(qū)間為空篷角，不用判斷恳蹲，也一定是回文串
        // [l + 1, r - 1] 一定至少有 2 個(gè)元素 等價(jià)于 l + 1 < r - 1嘉蕾，即 r - l >  2

        // 寫代碼的時(shí)候這樣寫：如果 [l + 1, r - 1]  的元素小于等于 1 個(gè)错忱，即 r - l <=  2 ，就不用做判斷了

        // 因?yàn)橹挥?1 個(gè)字符的情況在最開始做了判斷
        // 左邊界一定要比右邊界小儿普，因此右邊界從 1 開始
        for (int r = 1; r < len; r++) {
            for (int l = 0; l < r; l++) {
                // 區(qū)間應(yīng)該慢慢放大
                // 狀態(tài)轉(zhuǎn)移方程：如果頭尾字符相等并且中間也是回文
                // 在頭尾字符相等的前提下眉孩，如果收縮以后不構(gòu)成區(qū)間（最多只有 1 個(gè)元素）浪汪，直接返回 True 即可
                // 否則要繼續(xù)看收縮以后的區(qū)間的回文性
                // 重點(diǎn)理解 or 的短路性質(zhì)在這里的作用
                if (s.charAt(l) == s.charAt(r) && (r - l <= 2 || dp[l + 1][r - 1])) {
                    dp[l][r] = true;
                    if (r - l + 1 > longestPalindrome) {
                        longestPalindrome = r - l + 1;
                        longestPalindromeStr = s.substring(l, r + 1);
                    }
                }
            }
        }
        return longestPalindromeStr;
    }
}

寫完代碼以后死遭，請(qǐng)讀者在紙上寫下代碼運(yùn)行的流程呀潭，以字符串 'babad' 為例：

image.png

（草稿太潦草了蜗侈，大家將就看吧踏幻，懶得繪圖了该面，原因是太麻煩信卡，并且我覺得展示手寫草稿可能更有意義一些傍菇。）

說明：上面示例代碼填寫 dp 數(shù)組（二維狀態(tài)數(shù)組）是按照“從左到右、從上到下”的方向依次填寫的（你不妨打開我上面的 Python 示例代碼中的調(diào)試語句運(yùn)行一下驗(yàn)證）淮悼，當(dāng) “ s[l + 1, r - 1] 至少包含兩個(gè)元素” 即 r - l > 2 時(shí)袜腥，dp[l, r] 的值要看 d[[l + 1, r - 1] 羹令，即在 r - l > 2 的時(shí)候福侈，dp[l, r] 的值看“左下角”的值徐钠，只要按照“從左到右尝丐、從上到下”的方向依次填寫爹袁，當(dāng) r - l > 2 時(shí)，左下角就一定有值譬淳，這一點(diǎn)是動(dòng)態(tài)規(guī)劃算法得以有效的重要原因邻梆。

根據(jù)一個(gè)具體例子浦妄，在草稿紙上寫下（繪圖）代碼的運(yùn)行流程剂娄，有時(shí)是夠加深我們對(duì)算法的理解阅懦，并且也有助于調(diào)試代碼徘铝。

復(fù)雜度分析：

• 時(shí)間復(fù)雜度：。
• 空間復(fù)雜度：混埠，二維 dp 問題诗轻，一個(gè)狀態(tài)得用二維有序數(shù)對(duì)表示扳炬，因此空間復(fù)雜度是 恨樟。

方法四：Manacher 算法

維基百科中對(duì)于 Manacher 算法是這樣描述的：

[Manacher(1975)] 發(fā)現(xiàn)了一種線性時(shí)間算法劝术，可以在列出給定字符串中從字符串頭部開始的所有回文养晋。并且绳泉，Apostolico, Breslauer & Galil (1995) 發(fā)現(xiàn)零酪，同樣的算法也可以在任意位置查找全部最大回文子串四苇，并且時(shí)間復(fù)雜度是線性的方咆。因此峻呛，他們提供了一種時(shí)間復(fù)雜度為線性的最長(zhǎng)回文子串解法钩述。替代性的線性時(shí)間解決 Jeuring (1994), Gusfield (1997)提供的，基于后綴樹(suffix trees)职恳。也存在已知的高效并行算法放钦。

Manacher 算法，被中國(guó)程序員戲稱為“馬拉車”算法褂策。專門用于解決“最長(zhǎng)回文子串”問題斤寂，時(shí)間復(fù)雜度為 遍搞，事實(shí)上溪猿，“馬拉車”算法在思想上和“KMP”字符串匹配算法有相似之處诊县，都避免做了很多重復(fù)的工作护戳∠被模“KMP”算法也有一個(gè)很有意思的戲稱钳枕，帶有一點(diǎn)顏色。

挺有意思的一件事情是：我在學(xué)習(xí)“樹狀數(shù)組”和“Manacher 算法”的時(shí)候衔沼，都看了很多資料指蚁，但最后代碼實(shí)現(xiàn)的時(shí)候凝化，就只有短短十幾行搓劫。

理解 Manacher 算法最好的辦法，是根據(jù)查閱的關(guān)于 Manacher 算法的文章勤揩，自己在稿紙上寫寫畫畫陨亡，舉一些具體的例子深员，這樣 Manacher 算法就不難搞懂了辨液。

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

下面介紹 Manacher 算法的運(yùn)行流程鸽粉。

首先還是“中心擴(kuò)散法”的思想：回文串可分為奇數(shù)回文串和偶數(shù)回文串抓艳，它們的區(qū)別是：奇數(shù)回文串關(guān)于它的“中點(diǎn)”滿足“中心對(duì)稱”，偶數(shù)回文串關(guān)于它“中間的兩個(gè)點(diǎn)”滿足“中心對(duì)稱”儡首。為了避免對(duì)于回文串字符個(gè)數(shù)為奇數(shù)還是偶數(shù)的套路蔬胯。首先對(duì)原始字符串進(jìn)行預(yù)處理约谈，方法也很簡(jiǎn)單：添加分隔符。

第 1 步：對(duì)原始字符串進(jìn)行預(yù)處理（添加分隔符）

我們先給出具體的例子泼橘，看看如何添加分隔符炬灭。

例1：給字符串 "level" 添加分隔符 "#"重归。

答：字符串 "level" 添加分隔符 "#" 以后得到："#l#e#v#e#l#"鼻吮。

例2：給字符串 "noon" 添加分隔符 "#"。

答：字符串 "noon" 添加分隔符 "#" 以后得到："#n#o#o#n#"违柏。

我想你已經(jīng)看出來分隔符是如何添加的漱竖，下面是兩點(diǎn)說明馍惹。

1万矾、分隔符是一定是原始字符串中沒有出現(xiàn)過的字符勤众，這個(gè)分隔符的種類也只能有一個(gè)鲤脏，即你不能同時(shí)添加 "#" 和 "?" 作為分隔符猎醇；

2硫嘶、添加分隔符的方法是在字符串的首位置沦疾、尾位置和每個(gè)字符的“中間”都添加 個(gè)這個(gè)分隔符第队〉是可以很容易知道尸执，如果這個(gè)字符串的長(zhǎng)度是 len如失，那么添加的分隔符的個(gè)數(shù)就是 len + 1褪贵，得到的新的字符串的長(zhǎng)度就是 2 * len + 1竭鞍，顯然它一定是奇數(shù)。

為什么要添加分隔符冯乘？

1裆馒、首先是正確性：添加了分隔符以后的字符串的回文性質(zhì)與原始字符串是一樣的（這句話不是很嚴(yán)謹(jǐn)喷好，大家意會(huì)即可）；

2禾唁、其次是避免回文串長(zhǎng)度奇偶性的討論（馬上我們就會(huì)看到這一點(diǎn)是如何體現(xiàn)的）荡短。

第 2 步：得到 p 數(shù)組

p 數(shù)組可以通過填表得到掘托。以字符串 "abbabb" 為例闪盔，說明如何手動(dòng)計(jì)算得到 p 數(shù)組。假設(shè)我們要填的就是下面這張表听绳。

第 1 行 char 數(shù)組：這個(gè)數(shù)組是原始字符串加上分隔符以后的字符構(gòu)成的數(shù)組辫红。

第 2 行 index 數(shù)組：這個(gè)數(shù)組是char 數(shù)組的索引數(shù)組贴妻，我們后面要利用到它名惩，它的值就是索引編號(hào)娩鹉，從 開始。

下面我們來看看 p 數(shù)組應(yīng)該如何填寫个曙。首先我們定義“回文半徑”垦搬。

回文半徑：以 char[i] 作為回文中心猴贰，同時(shí)向左邊、向右邊進(jìn)行“中心擴(kuò)散”瑟捣，直到“不能構(gòu)成回文串”或“觸碰到字符串邊界”為止蝶柿，能擴(kuò)散的步數(shù) + 1（這個(gè) 1 表示“中心”） 交汤，即定義為 p 數(shù)組的值芙扎，也稱之為“回文半徑戒洼。

• 用上面的例子，我們首先填 p[0]寥掐。

以 char[0] = '#'為中心召耘，同時(shí)向左邊向右擴(kuò)散污它，走 1 步就碰到邊界了衫贬，因此“能擴(kuò)散的步數(shù)”為0固惯，“能擴(kuò)散的步數(shù) + 1 = 1”缴守，因此 p[0] = 1斧散；

• 下面填寫 p[1] 鸡捐。

以 char[1] = 'a' 為中心麻裁，同時(shí)向左邊向右擴(kuò)散煎源，走 1 步，左右都是 "#"歇僧，構(gòu)成回文子串祸轮，于是再繼續(xù)同時(shí)向左邊向右邊擴(kuò)散侥钳，左邊就碰到邊界了舷夺，因此“能擴(kuò)散的步數(shù)”為1给猾，“能擴(kuò)散的步數(shù) + 1 = 2”耙册，因此 p[1] = 2；

• 下面填寫 p[2] 帝际。

以 char[2] = '#' 為中心蹲诀，同時(shí)向左邊向右擴(kuò)散脯爪，走 1 步痕慢，左邊是 "a"掖举，右邊是 "b"塔次，不匹配励负，因此“能擴(kuò)散的步數(shù)”為 匕得，“能擴(kuò)散的步數(shù) + 1 = 1”，因此 p[2] = 1攒发；

• 下面填寫 p[3]惠猿。

以 char[3] = 'b' 為中心偶妖，同時(shí)向左邊向右擴(kuò)散趾访，走 1 步扼鞋，左右兩邊都是 “#”云头，構(gòu)成回文子串淫半，繼續(xù)同時(shí)向左邊向右擴(kuò)散科吭，左邊是 "a"对人，右邊是 "b"牺弄，不匹配，因此“能擴(kuò)散的步數(shù)”為 1 ，“能擴(kuò)散的步數(shù) + 1 = 2”培慌，因此 p[3] = 2吵护；

• 下面填寫 p[4]馅而。

以 char[4] = '#' 為中心瓮恭，同時(shí)向左邊向右擴(kuò)散屯蹦，最多可以走 4 步登澜，左邊到達(dá)邊界，因此“能擴(kuò)散的步數(shù)”為4购撼，“能擴(kuò)散的步數(shù) + 1 = 5”迂求，因此 p[4] = 5锁摔。

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

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

p-1 數(shù)組很簡(jiǎn)單了芹枷，把 p 數(shù)組對(duì)應(yīng)位置的值 -1 就行了鸳慈。是不是覺得有點(diǎn)“繞”走芋，剛才每一步要 + 1 ，現(xiàn)在每一步要 -1肋杖，這不是吃飽了撐的嗎挖函？你說的沒錯(cuò)挪圾。這里得到 p 數(shù)組不過就是為了給“回文半徑”一個(gè)定義而已哲思。

即：p 數(shù)組可以稱之為“回文半徑數(shù)組”。

于是我們得到如下表格：

• p 數(shù)組的最大值是 ，對(duì)應(yīng)的 “最長(zhǎng)回文子串” 是 "#b#b#a#b#b#"靠益；
• p - 1 數(shù)組的最大值是 胧后，就對(duì)應(yīng)了原字符串 "abbabb" 的 “最長(zhǎng)回文子串” ："bbabb"壳快。

規(guī)律如下：

p -1 數(shù)組的最大值就是“最長(zhǎng)回文子串”的長(zhǎng)度。即“最大回文半徑”知道了瘤旨，減 1 就是原字符串的“最長(zhǎng)回文子串”的長(zhǎng)度存哲。

• 可以在得到 p 數(shù)組的過程中記錄這個(gè)最大值祟偷，并且記錄最長(zhǎng)回文子串修肠。

那么如何編寫程序得到 p 數(shù)組呢婚惫？其實(shí)也不難先舷，即使用“回文串”的性質(zhì)避免重復(fù)計(jì)算蒋川。下面這張圖展示了這個(gè)思想：

image.png

{:width="500"}
{:align=center}

上面這張圖畫得仔細(xì)一點(diǎn)是下面這張圖：

image.png

{:width="700"}
{:align=center}

這里 i 和 j 關(guān)于 id 中心對(duì)稱：即 j = 2 * id - i缸浦。上面的兩張圖表示的意思是：p[i] 的值可以根據(jù) p[j] 得到氮兵。因?yàn)槲覀儽闅v一個(gè)字符串的方向是“從左到右”泣栈，故數(shù)組 p 后面的值根據(jù)前面的值得來南片，這個(gè)思路沒有問題。

接下來要介紹 id 和 mx 的含義了：

1薪缆、id ：從開始到現(xiàn)在使用“中心擴(kuò)散法”能得到的“最長(zhǎng)回文子串”的中心的位置拣帽；

2诞外、mx：從開始到現(xiàn)在使用“中心擴(kuò)散法”能得到的“最長(zhǎng)回文子串”能延伸到的最右端的位置峡谊。容易知道 mx = id + p[id]刊苍。

先從最簡(jiǎn)單的情況開始：

1正什、當(dāng) id < i < mx 的時(shí)候婴氮，此時(shí) id 之前的 p 值都已經(jīng)計(jì)算出來了址晕，我們利用已經(jīng)計(jì)算出來的 p 值來計(jì)算當(dāng)前位置的 p 值距芬。

由于以 j 為中心的最長(zhǎng)子回文串护赊，落在了以 id 為中心的最長(zhǎng)子回文串內(nèi)骏啰，由于 i 和 j 對(duì)稱判耕， 故索引 i 附近的回文串可以與索引 j 附近的回文串建立一一對(duì)應(yīng)的關(guān)系翘骂。

• 如果 j 的回文串很短雏胃，在 mx 關(guān)于 id 的對(duì)稱點(diǎn)之前結(jié)束瞭亮，一定有 dp[i]=dp[j]，如上圖所示仙蚜；
• 如果 j 的回文串很長(zhǎng)委粉，此時(shí) dp[i] 的值不會(huì)超過 i 與 mx 之間的距離： mx - i贾节，此時(shí)想一下 mx 是 以 id 為中心的最長(zhǎng)回文子串的“最右邊界”栗涂，就不難理解了祈争，如下圖所示 菩混。

如果 p[j] 很大的話，即當(dāng) p[j] >= mx - i 的時(shí)候疚脐，以 s[j] 為中心的回文子串不一定完全包含于以 s[id] 為中心的回文子串中亮曹，但是基于對(duì)稱性可知照卦，以 s[i] 為中心的回文子串役耕，其向右至少會(huì)擴(kuò)張到 mx 的位置瞬痘，也就是說 p[i] >= mx - i框全。至于 mx 之后的部分是否對(duì)稱干签，就只能老老實(shí)實(shí)去匹配了容劳。

image.png

{:width="700"}
{:align=center}

把上面說的整理一下竭贩，當(dāng) p[j] 的范圍很小的時(shí)候留量，有 p[i] = p[j]，p[i] 的值再大不過超過 mx - i ：

if i < mx:
    p[i] = min(p[2 * id - i], mx - i);

2寝凌、當(dāng) i >= mx 的時(shí)候较木，此時(shí)也只能老老實(shí)實(shí)使用“中心擴(kuò)散法”來逐漸得到 p 數(shù)組的值伐债，同時(shí)記錄 id 和 mx。

以上可以合并成一行代碼：

p[i] = mx > i ? min(p[2 * id - i], mx - i) : 1;

這一行代碼拆開來看就是：

如果 mx > i, 則 p[i] = min(p[2 * id - i], mx - i)萎馅，否則 p[i] = 1糜芳。

參考代碼 3：

public class Solution {

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

    public String longestPalindrome(String s) {
        int len = s.length();
        if (len == 0) {
            return "";
        }
        String sDivided = generateSDivided(s, '#');
        int slen = sDivided.length();
        int[] p = new int[slen];
        int mx = 0;
        // id 是由 mx 決定的荆责，所以不用初始化做院，只要聲明就可以了
        int id = 0;
        int longestPalindrome = 1;
        String longestPalindromeStr = s.substring(0, 1);
        for (int i = 0; i < slen; i++) {
            if (i < mx) {
                // 這一步是 Manacher 算法的關(guān)鍵所在山憨，一定要結(jié)合圖形來理解
                // 這一行代碼是關(guān)鍵，可以把兩種分類討論的情況合并
                p[i] = Integer.min(p[2 * id - i], mx - i);
            } else {
                // 走到這里玛迄，只可能是因?yàn)?i = mx
                if (i > mx) {
                    throw new IllegalArgumentException("程序出錯(cuò)蓖议！");
                }
                p[i] = 1;
            }
            // 老老實(shí)實(shí)去匹配勒虾，看新的字符
            while (i - p[i] >= 0 && i + p[i] < slen && sDivided.charAt(i - p[i]) == sDivided.charAt(i + p[i])) {
                p[i]++;
            }
            // 我們想象 mx 的定義修然，它是遍歷過的 i 的 i + p[i] 的最大者
            // 寫到這里愕宋，我們發(fā)現(xiàn)，如果 mx 的值越大囤捻，
            // 進(jìn)入上面 i < mx 的判斷的可能性就越大蝎土，這樣就可以重復(fù)利用之前判斷過的回文信息了
            if (i + p[i] > mx) {
                mx = i + p[i];
                id = i;
            }

            if (p[i] - 1 > longestPalindrome) {
                longestPalindrome = p[i] - 1;
                longestPalindromeStr = sDivided.substring(i - p[i] + 1, i + p[i]).replace("#", "");
            }
        }
        return longestPalindromeStr;
    }
}

復(fù)雜度分析：

• 時(shí)間復(fù)雜度：誊涯，由于 Manacher 算法只有在遇到還未匹配的位置時(shí)才進(jìn)行匹配，已經(jīng)匹配過的位置不再匹配慷嗜，所以對(duì)于對(duì)于字符串S 的每一個(gè)位置庆械，都只進(jìn)行一次匹配，所以算法的總體復(fù)雜度為 沐序。
• 空間復(fù)雜度：策幼。