title: 經(jīng)典算法問題：最長回文子串之 Manacher 算法
date: 2019-02-17 08:00:00
author: liwei
top: false
mathjax: true
categories: leetcode 題解
tags:

動(dòng)態(tài)規(guī)劃
字符串
permalink: leetcode-tag/longest-palindromic-substring

經(jīng)典算法問題：最長回文子串之 Manacher 算法

維基百科中對(duì)于“最長回文子串”介紹如下。

在計(jì)算機(jī)科學(xué)中，最長回文子串或最長對(duì)稱因子問題是在一個(gè)字符串中查找一個(gè)最長連續(xù)子串，這個(gè)子串必須是回文。例如“banana”最長回文子串是“anana”。最長回文子串并不能保證是唯一的，

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

LeetCode 第 5 題就是“最長回文子串”的模板題。

LeetCode 第 5 題：最長回文子串

傳送門：5. 最長回文子串

給定一個(gè)字符串 s，找到 s 中最長的回文子串。你可以假設(shè) s 的最大長度為 1000。

示例 1：
輸入: "babad"
輸出: "bab"
注意: "aba" 也是一個(gè)有效答案。
示例 2：
輸入: "cbbd"
輸出: "bb"

回文串可分為奇數(shù)回文串和偶數(shù)回文串。
它們的區(qū)別是：奇數(shù)回文串關(guān)于它的“中點(diǎn)”滿足“中心對(duì)稱”，偶數(shù)回文串關(guān)于它“中間的兩個(gè)點(diǎn)”滿足“中心對(duì)稱”。
我們?cè)诰唧w判定一個(gè)字符串是否是回文串的時(shí)候，常常會(huì)不自覺地考慮到它們之間的這個(gè)小的差別。

思路1：暴力匹配 Brute Force。

暴力匹配，雖然聽起來并不是那么友好，但是我個(gè)人認(rèn)為暴力解法雖然時(shí)間復(fù)雜度很高，但是它簡(jiǎn)單粗暴，編寫正確的概率其實(shí)是很高的，完全可以使用暴力匹配算法檢驗(yàn)我們編寫的算法的正確性，并且在優(yōu)化正確的前提下，通過和暴力匹配的比較，也可以體現(xiàn)我們優(yōu)化算法的性能優(yōu)勢(shì)。
當(dāng)然，“最長回文子串”在 LeetCode 上有標(biāo)準(zhǔn)的問題，我們編寫好算法以后，可以提交到 LeetCode 上，運(yùn)行 LeetCode 的測(cè)試用例檢驗(yàn)我們實(shí)現(xiàn)的算法。

思路2：中心擴(kuò)散法。想法很簡(jiǎn)單，就是遍歷每一個(gè)索引，以這個(gè)索引為中心，看看往兩邊擴(kuò)散，最多能擴(kuò)散多長的字符串。具體做法是利用“回文串”中心對(duì)稱的特點(diǎn)，在枚舉子串的過程中進(jìn)行剪枝，在具體解這個(gè)問題的過程中，我們就要對(duì)可能產(chǎn)生的回文串是奇數(shù)長度和偶數(shù)長度進(jìn)行考量，但是完全可以設(shè)計(jì)一種方法，兼容兩種情況。

設(shè)計(jì)一個(gè)方法：傳入兩個(gè)索引編號(hào)參數(shù)，傳入重合的索引編碼，進(jìn)行中心擴(kuò)散，得到的最長回文子串就是奇數(shù)長度的。傳入相鄰的索引編碼，進(jìn)行中心擴(kuò)散，得到的最長回文子串就是偶數(shù)長度的。
具體編碼細(xì)節(jié)在代碼的注釋中已經(jīng)體現(xiàn)。

Python 代碼：

class Solution:
    def longestPalindrome(self, s):
        """
        最長回文子串，比較容易想到的就是中心擴(kuò)散法
        :type s: str
        :rtype: str
        """
        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)前找到的最長回文子串
            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ù)
        right = left + 1 的時(shí)候，表示回文中心是任意一個(gè)字符，回文串的長度是偶數(shù)
        :param s:
        :param size:
        :param left:
        :param right:
        :return:
        """
        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

Java 代碼：

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);
    }
}

思路3：動(dòng)態(tài)規(guī)劃。

有了計(jì)算機(jī)的幫助，解決這類“最優(yōu)子結(jié)構(gòu)”問題，當(dāng)然是在“動(dòng)態(tài)規(guī)劃”的能力范圍內(nèi)。我們只要找準(zhǔn)“狀態(tài)”的定義，找到“狀態(tài)轉(zhuǎn)移方程”就可以了。當(dāng)然，在實(shí)現(xiàn)的過程中，還有一些小細(xì)節(jié)。

定義狀態(tài)：s[i, j] ：表示原始字符串的一個(gè)子串，i、j分別是索引，使用閉區(qū)間表示包括區(qū)間左右端點(diǎn)。

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

狀態(tài)轉(zhuǎn)移方程：在 dp[i, j] = true 的時(shí)候， dp[i + 1, j - 1] = true，因此，如果已知 dp[i + 1, j - 1]，就可以通過比較 s[i] 和 s[j] 并且考慮 dp[i + 1, j - 1] 進(jìn)而得到 dp[i, j]。

如果 s[i, j] 是一個(gè)回文串，例如 “abccba”，那么 s[i+1, j-1] 也一定是一個(gè)回文串，根據(jù)這個(gè)遞歸的性質(zhì)，我們可以寫出狀態(tài)轉(zhuǎn)移方程。

dp[i, j] = dp[i+1, j-1]，當(dāng)然，此時(shí)我們要保證 [i+1, j-1] 能夠形成區(qū)間，因此有

i+1<=j-1，整理得 i-j <= -2，或者 j-i >=2。

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

Python 代碼：

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        size = len(s)
        if size <= 1:
            return s
        # 二維 dp 問題
        # 狀態(tài)：dp[i,j]: s[i:j] 包括 i，j ，表示的字符串是不是回文串
        dp = [[False for _ in range(size)] for _ in range(size)]

        longest_l = 1
        res = s[0]

        for i in range(size):
            for j in range(i):
                # 狀態(tài)轉(zhuǎn)移方程：如果頭尾字符相等并且中間也是回文
                # 或者中間的長度小于等于 1
                if s[j] == s[i] and (j >= i - 2 or dp[j + 1][i - 1]):
                    dp[j][i] = True
                    if i - j + 1 > longest_l:
                        longest_l = i - j + 1
                        res = s[j:i + 1]
        return res

Java 代碼：

public class Solution2 {

    public String longestPalindrome(String s) {
        int len = s.length();
        if (len == 0) {
            return "";
        }
        int longestPalindrome = 1;
        String longestPalindromeStr = s.substring(0, 1);
        boolean[][] dp = new boolean[len][len];
        // abcdedcba
        //   j   i
        // 如果 dp[j,i] = true 那么 dp[j+1,i-1] 也一定為 true
        // [j+1,i-1] 一定要構(gòu)成至少兩個(gè)元素額區(qū)間（ 1 個(gè)元素的區(qū)間，s.charAt(i)==s.charAt(j) 已經(jīng)判斷過了）
        // 即 j+1 < i-1，即 i > j + 2 (不能取等號(hào)，取到等號(hào)，就退化成 1 個(gè)元素的情況了)
        // 應(yīng)該反過來寫
        for (int i = 0; i < len; i++) {
            for (int j = 0; j <= i; j++) {
                // 區(qū)間應(yīng)該慢慢放大
                if (s.charAt(i) == s.charAt(j) && (i <= j + 2 || dp[j + 1][i - 1])) {
                    // 寫成 dp[j][i] 就大錯(cuò)特錯(cuò)了，不要順手寫習(xí)慣了
                    dp[j][i] = true;
                    if (i - j + 1 > longestPalindrome) {
                        longestPalindrome = i - j + 1;
                        longestPalindromeStr = s.substring(j, i + 1);
                    }
                }
            }
        }
        return longestPalindromeStr;
    }
}

思路4：專門解決回文串的一個(gè)著名算法 Manacher 算法。

很有意思的一件事情是：Manacher 算法被中國程序員戲稱為“馬拉車”算法。事實(shí)上，“馬拉車”算法在思想上和“KMP”字符串匹配算法一樣，都避免做了很多重復(fù)的工作，“KMP”算法也有一個(gè)很有意思的戲稱。

Manacher 算法就是專門解決“最長回文子串”的一個(gè)算法，它的時(shí)間復(fù)雜度可以達(dá)到 $O(n)$ ，雖然是特性的算法，并不具有普遍性，但它的代碼量小，處理技巧優(yōu)雅，是值得我們學(xué)習(xí)的。

挺有意思的一件事情是，我在學(xué)習(xí)“樹狀數(shù)組”和“Manacher 算法”的時(shí)候，都是看了很多很多資料，但是到最后，代碼實(shí)現(xiàn)的時(shí)候，就只有短短十幾行，另外“KMP 算法”也是如此。

Manacher 算法

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

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

在還沒有實(shí)現(xiàn)算法之前，我們先要弄清楚算法的運(yùn)行流程，即給我們一個(gè)具體的字符串，我們通過稿紙演算的方式，應(yīng)該如何得到給定字符串的最長子回文串。

理解 Manacher 算法最好的辦法，其實(shí)是根據(jù)一些關(guān)于 Manacher 算法的文章，自己寫寫畫畫，最好能產(chǎn)生一些輸出，畫畫圖，舉一些具體的例子，這樣 Manacher 算法就不難搞懂了。

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

回文串可分為奇數(shù)回文串和偶數(shù)回文串，它們的區(qū)別是：奇數(shù)回文串關(guān)于它的“中點(diǎn)”滿足“中心對(duì)稱”，偶數(shù)回文串關(guān)于它“中間的兩個(gè)點(diǎn)”滿足“中心對(duì)稱”。我們?cè)诰唧w判定一個(gè)字符串是否是回文串的時(shí)候，常常會(huì)不自覺地考慮到它們之間的這個(gè)小的差別。

第 1 步：預(yù)處理，添加分隔符

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

例1：給字符串 "bob" 添加分隔符 "#"。

答："bob" 添加分隔符 "#" 以后得到："#b#o#b#"。

再看一個(gè)例子：

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

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

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

1、分隔符是字符串中沒有出現(xiàn)過的字符，這個(gè)分隔符的種類只有一個(gè)，即你不能同時(shí)添加 "#" 和 "?" 作為分隔符；

2、在字符串的首位置、尾位置和每個(gè)字符的“中間”都添加 $1$ 個(gè)這個(gè)分隔符，可以很容易知道，如果這個(gè)字符串的長度是 len，那么添加的分隔符的個(gè)數(shù)就是 len + 1，得到的新的字符串的長度就是 2len + 1，顯然它一定是奇數(shù)。

為什么要添加分隔符？

1、首先是正確性：添加了分隔符以后的字符串的回文性質(zhì)與原始字符串是一樣的。

2、其實(shí)是避免奇偶數(shù)討論，對(duì)于使用“中心擴(kuò)散法”判定回文串的時(shí)候，長度為奇數(shù)和偶數(shù)的判定是不同的，添加分隔符可以避免對(duì)奇偶性的討論。

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

首先，我們先來看一下如何填表。以字符串 "abbabb" 為例，說明如何手動(dòng)計(jì)算得到 p 數(shù)組。假設(shè)我們要填的就是下面這張表。

char	#	a	#	b	#	b	#	a	#	b	#	b	#
index	0	1	2	3	4	5	6	7	8	9	10	11	12
p	1	2	1	2	5
p-1

第 1 行 char 數(shù)組：這個(gè)數(shù)組就是待檢測(cè)字符串加上分隔符以后的字符構(gòu)成的數(shù)組。

第 2 行 index 數(shù)組：這個(gè)數(shù)組是索引數(shù)組，我們后面要利用到它，填寫即索引從 0 開始寫就好了。

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

回文半徑：以 char[i] 作為回文中心，同時(shí)向左邊、向右邊進(jìn)行擴(kuò)散，直到不能構(gòu)成回文串或者觸碰到邊界為止，能擴(kuò)散的步數(shù) + 1 ，即定義為 p 數(shù)組索引的值，也稱之為回文半徑。

以上面的例子，我們首先填。p[0]，以 char[0] = '#'為中心，同時(shí)向左邊向右擴(kuò)散，走 1 步就碰到邊界了，因此“能擴(kuò)散的步數(shù)”為0，“能擴(kuò)散的步數(shù) + 1 = 1”，因此 p[0] = 1；

char	#	a	#	b	#	b	#	a	#	b	#	b	#
index	0	1	2	3	4	5	6	7	8	9	10	11	12
p	1
p-1

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

char	#	a	#	b	#	b	#	a	#	b	#	b	#
index	0	1	2	3	4	5	6	7	8	9	10	11	12
p	1	2
p-1

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

char	#	a	#	b	#	b	#	a	#	b	#	b	#
index	0	1	2	3	4	5	6	7	8	9	10	11	12
p	1	2	1
p-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；

char	#	a	#	b	#	b	#	a	#	b	#	b	#
index	0	1	2	3	4	5	6	7	8	9	10	11	12
p	1	2	1	2
p-1

下面填寫 p[4]，以 char[4]='#' 為中心，同時(shí)向左邊向右擴(kuò)散，可以知道可以同時(shí)走 4 步，左邊到達(dá)邊界，因此“能擴(kuò)散的步數(shù)”為4，“能擴(kuò)散的步數(shù) + 1 = 5”，因此 p[4] = 5。

char	#	a	#	b	#	b	#	a	#	b	#	b	#
index	0	1	2	3	4	5	6	7	8	9	10	11	12
p	1	2	1	2	5
p-1

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

char	#	a	#	b	#	b	#	a	#	b	#	b	#
index	0	1	2	3	4	5	6	7	8	9	10	11	12
p	1	2	1	2	5	2	1	6	1	2	3	2	1
p-1

p-1 數(shù)組很簡(jiǎn)單了，把 p 數(shù)組的數(shù) -1 就行了。實(shí)際上直接把能走的步數(shù)記錄下來就好了。不過就是為了給“回文半徑”一個(gè)定義而已。

于是我們得到如下表格：

char	#	a	#	b	#	b	#	a	#	b	#	b	#
index	0	1	2	3	4	5	6	7	8	9	10	11	12
p	1	2	1	2	5	2	1	6	1	2	3	2	1
p-1	0	1	0	1	4	1	0	5	0	1	2	1	0

于是：數(shù)組 p -1 的最大值就是最長的回文子串，可以在得到 p 數(shù)組的過程中記錄這個(gè)最大值，并且記錄最長回文子串。

如何編寫程序得到 p 數(shù)組？

通過 p 數(shù)組我們就可以找到回文串的最大值，就能確定最長回文子串了。那么下面我們就來看如何編碼求 p 數(shù)組，需要設(shè)置兩個(gè)輔助變量 mx 和 id ，它們的含義分別如下：

id ：從開始到現(xiàn)在使用中心擴(kuò)散法得到的最長回文子串的中心的位置；

mx：從開始到現(xiàn)在使用中心擴(kuò)散法得到的最長回文子串能延伸到的最右端的位置。

數(shù)組 p 的值就與它們兩個(gè)有關(guān)，這個(gè)算法的最核心的一行如下：

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。

Manacher 算法-1

這里 2 * id - i 是 i 關(guān)于 id 的對(duì)稱索引。

我們通過分類討論，就可以得到這個(gè)等式。一開始，我們是不能偷懶的，老老實(shí)實(shí)使用中心擴(kuò)散法來逐漸得到 p 數(shù)組的值，同時(shí)記錄 id 和 mx。當(dāng)我們要考察的索引 i 超過了 mx 的時(shí)候，如下圖，我們就可以偷點(diǎn)懶了。根據(jù)回文串的特點(diǎn)，i 關(guān)于 mx 的對(duì)稱點(diǎn)附近的情況我們已經(jīng)計(jì)算出來了，因此，我們可以分如下兩種情況討論。

討論從一個(gè)中間的情況開始：

1、首先當(dāng) i 位于 id 和 mx 之間時(shí)，此時(shí) id 之前的 p 值都已經(jīng)計(jì)算出來了，我們利用已經(jīng)計(jì)算出來的 p 值來計(jì)算當(dāng)前考慮的位置的 p 值。

因?yàn)槭腔匚拇?，因此?mx 的對(duì)稱點(diǎn)與 id 這個(gè)區(qū)間內(nèi)，一定有一個(gè)點(diǎn)與 j 相等，這個(gè)點(diǎn)的索引就是 2 * id - i。

當(dāng) id < i < mx 的時(shí)候：

引入 j，如果 j 的回文串很短，在 mx 關(guān)于 id 的對(duì)稱點(diǎn)之前結(jié)束。

此時(shí) j = 2 * id - i，

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

當(dāng) j 的范圍很小的時(shí)候，取 p[2 * id - i] ，此時(shí) p[i] = p[j]。

2、當(dāng) mx - i > p[j] 的時(shí)候，以 s[j] 為中心的回文子串包含在以 s[id] 為中心的回文子串中，由于 i 和 j 對(duì)稱，以 s[i] 為中心的回文子串必然包含在以 s[id] 為中心的回文子串中，所以必有 p[i] = p[j]，見下圖。

Manacher 算法-2

Manacher 算法-3

3、當(dāng) p[j] >= mx - i 的時(shí)候，以 s[j] 為中心的回文子串不一定完全包含于以 s[id] 為中心的回文子串中，但是基于對(duì)稱性可知，下圖中兩個(gè)綠框所包圍的部分是相同的，也就是說以 s[i] 為中心的回文子串，其向右至少會(huì)擴(kuò)張到 mx 的位置，也就是說 p[i] >= mx - i。至于 mx 之后的部分是否對(duì)稱，就只能老老實(shí)實(shí)去匹配了。

Manacher 算法-4

4、對(duì)于 mx <= i 的情況，無法對(duì) p[i] 做更多的假設(shè)，只能從 p[i] = 1 開始，然后再去匹配了。

Java 代碼：

/**
 * 使用 Manacher 算法
 */
public class Solution3 {

    /**
     * 創(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;
    }
}