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

暴力解法雖然時間復雜度高，但是思路清晰、編寫簡單，因為編寫的正確性高，完全可以使用暴力匹配算法檢驗我們編寫的算法的正確性。

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

方法二：中心擴散法

中心擴散法的想法很簡單：遍歷每一個索引，以這個索引為中心，利用“回文串”中心對稱的特點，往兩邊擴散，看最多能擴散多遠。要注意一個細節(jié)：回文串的長度可能是奇數(shù)，也可能是偶數(shù)。

LeetCode 第 5 題：中心擴散法

我們完全可以設計一個方法，兼容以上兩種情況：

1、如果傳入重合的索引編碼，進行中心擴散，此時得到的最長回文子串的長度是奇數(shù)；

2、如果傳入相鄰的索引編碼，進行中心擴散，此時得到的最長回文子串的長度是偶數(shù)。

參考代碼 1：

具體編碼細節(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)

            # 當前找到的最長回文子串
            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ù)
        right = left + 1 的時候，此時回文中心是任意一個字符，回文串的長度是偶數(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)的時候，是第 1 個滿足 s.charAt(l) != s.charAt(r) 的時候
        // 所以，不能取 l，不能取 r
        return s.substring(l + 1, r);
    }
}

復雜度分析：

• 時間復雜度：。
• 空間復雜度：。

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

推薦理由：暴力解法太 naive，中心擴散不普適，Manacher 就更不普適了，是專門解這個問題的方法。而用動態(tài)規(guī)劃我認為是最有用的，可以幫助你舉一反三的方法。

補充說明：Manacher 算法有興趣的朋友們可以了解一下，有人就借助它的第一步字符串預處理思想，解決了 LeetCode 第 4 題。因此以上推薦僅代表個人觀點。

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

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

記號說明： 下文中，使用記號 s[l, r] 表示原始字符串的一個子串，l、r 分別是區(qū)間的左右邊界的索引值，使用左閉、右閉區(qū)間表示左右邊界可以取到。舉個例子，當 s = 'babad' 時，s[0, 1] = 'ba' ，s[2, 4] = 'bad'。

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

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

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

首先，我們很清楚一個事實：

1、當子串只包含 個字符，它一定是回文子串；

2、當子串包含 2 個以上字符的時候：如果 s[l, r] 是一個回文串，例如 “abccba”，那么這個回文串兩邊各往里面收縮一個字符（如果可以的話）的子串 s[l + 1, r - 1] 也一定是回文串，即：如果 dp[l][r] == true 成立，一定有 dp[l + 1][r - 1] = true 成立。

根據(jù)這一點，我們可以知道，給出一個子串 s[l, r] ，如果 s[l] != s[r]，那么這個子串就一定不是回文串。如果 s[l] == s[r] 成立，就接著判斷 s[l + 1] 與 s[r - 1]，這很像中心擴散法的逆方法。

事實上，當 s[l] == s[r] 成立的時候，dp[l][r] 的值由 dp[l + 1][r - l] 決定，這一點也不難思考：當左右邊界字符串相等的時候，整個字符串是否是回文就完全由“原字符串去掉左右邊界”的子串是否回文決定。但是這里還需要再多考慮一點點：“原字符串去掉左右邊界”的子串的邊界情況。

1、當原字符串的元素個數(shù)為 個的時候，如果左右邊界相等，那么去掉它們以后，只剩下 個字符，它一定是回文串，故原字符串也一定是回文串；

2、當原字符串的元素個數(shù)為 個的時候，如果左右邊界相等，那么去掉它們以后，只剩下 個字符，顯然原字符串也一定是回文串。

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

綜上，如果一個字符串的左右邊界相等，以下二者之一成立即可：
1、去掉左右邊界以后的字符串不構(gòu)成區(qū)間，即“ s[l + 1, r - 1] 至少包含兩個元素”的反面，即 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]))

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

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

具體編碼細節(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 ，表示的字符串是不是回文串
        # 設置為 None 是為了方便調(diào)試，看清楚代碼執(zhí)行流程
        dp = [[False for _ in range(size)] for _ in range(size)]

        longest_l = 1
        res = s[0]

        # 因為只有 1 個字符的情況在最開始做了判斷
        # 左邊界一定要比右邊界小，因此右邊界從 1 開始
        for r in range(1, size):
            for l in range(r):
                # 狀態(tài)轉(zhuǎn)移方程：如果頭尾字符相等并且中間也是回文
                # 在頭尾字符相等的前提下，如果收縮以后不構(gòu)成區(qū)間（最多只有 1 個元素），直接返回 True 即可
                # 否則要繼續(xù)看收縮以后的區(qū)間的回文性
                # 重點理解 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
        // 關鍵在這里：[l + 1, r - 1] 一定至少有 2 個元素才有判斷的必要
        // 因為如果 [l + 1, r - 1] 只有一個元素，不用判斷，一定是回文串
        // 如果 [l + 1, r - 1] 表示的區(qū)間為空，不用判斷，也一定是回文串
        // [l + 1, r - 1] 一定至少有 2 個元素 等價于 l + 1 < r - 1，即 r - l >  2

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

        // 因為只有 1 個字符的情況在最開始做了判斷
        // 左邊界一定要比右邊界小，因此右邊界從 1 開始
        for (int r = 1; r < len; r++) {
            for (int l = 0; l < r; l++) {
                // 區(qū)間應該慢慢放大
                // 狀態(tài)轉(zhuǎn)移方程：如果頭尾字符相等并且中間也是回文
                // 在頭尾字符相等的前提下，如果收縮以后不構(gòu)成區(qū)間（最多只有 1 個元素），直接返回 True 即可
                // 否則要繼續(xù)看收縮以后的區(qū)間的回文性
                // 重點理解 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;
    }
}

寫完代碼以后，請讀者在紙上寫下代碼運行的流程，以字符串 'babad' 為例：

image.png

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

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

根據(jù)一個具體例子，在草稿紙上寫下（繪圖）代碼的運行流程，有時是夠加深我們對算法的理解，并且也有助于調(diào)試代碼。

復雜度分析：

• 時間復雜度：。
• 空間復雜度：，二維 dp 問題，一個狀態(tài)得用二維有序數(shù)對表示，因此空間復雜度是 。

方法四：Manacher 算法

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

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

Manacher 算法，被中國程序員戲稱為“馬拉車”算法。專門用于解決“最長回文子串”問題，時間復雜度為 ，事實上，“馬拉車”算法在思想上和“KMP”字符串匹配算法有相似之處，都避免做了很多重復的工作。“KMP”算法也有一個很有意思的戲稱，帶有一點顏色。

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

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

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

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

首先還是“中心擴散法”的思想：回文串可分為奇數(shù)回文串和偶數(shù)回文串，它們的區(qū)別是：奇數(shù)回文串關于它的“中點”滿足“中心對稱”，偶數(shù)回文串關于它“中間的兩個點”滿足“中心對稱”。為了避免對于回文串字符個數(shù)為奇數(shù)還是偶數(shù)的套路。首先對原始字符串進行預處理，方法也很簡單：添加分隔符。

第 1 步：對原始字符串進行預處理（添加分隔符）

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

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

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

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

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

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

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

2、添加分隔符的方法是在字符串的首位置、尾位置和每個字符的“中間”都添加 個這個分隔符?？梢院苋菀字?，如果這個字符串的長度是 len，那么添加的分隔符的個數(shù)就是 len + 1，得到的新的字符串的長度就是 2 * len + 1，顯然它一定是奇數(shù)。

為什么要添加分隔符？

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

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

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

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

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

第 2 行 index 數(shù)組：這個數(shù)組是char 數(shù)組的索引數(shù)組，我們后面要利用到它，它的值就是索引編號，從 開始。

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

回文半徑：以 char[i] 作為回文中心，同時向左邊、向右邊進行“中心擴散”，直到“不能構(gòu)成回文串”或“觸碰到字符串邊界”為止，能擴散的步數(shù) + 1（這個 1 表示“中心”） ，即定義為 p 數(shù)組的值，也稱之為“回文半徑。

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

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

• 下面填寫 p[1] 。

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

• 下面填寫 p[2] 。

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

• 下面填寫 p[3]。

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

• 下面填寫 p[4]。

以 char[4] = '#' 為中心，同時向左邊向右擴散，最多可以走 4 步，左邊到達邊界，因此“能擴散的步數(shù)”為4，“能擴散的步數(shù) + 1 = 5”，因此 p[4] = 5。

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

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

p-1 數(shù)組很簡單了，把 p 數(shù)組對應位置的值 -1 就行了。是不是覺得有點“繞”，剛才每一步要 + 1 ，現(xiàn)在每一步要 -1，這不是吃飽了撐的嗎？你說的沒錯。這里得到 p 數(shù)組不過就是為了給“回文半徑”一個定義而已。

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

于是我們得到如下表格：

• p 數(shù)組的最大值是 ，對應的 “最長回文子串” 是 "#b#b#a#b#b#"；
• p - 1 數(shù)組的最大值是 ，就對應了原字符串 "abbabb" 的 “最長回文子串” ："bbabb"。

規(guī)律如下：

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

• 可以在得到 p 數(shù)組的過程中記錄這個最大值，并且記錄最長回文子串。

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

image.png

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

上面這張圖畫得仔細一點是下面這張圖：

image.png

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

這里 i 和 j 關于 id 中心對稱：即 j = 2 * id - i。上面的兩張圖表示的意思是：p[i] 的值可以根據(jù) p[j] 得到。因為我們遍歷一個字符串的方向是“從左到右”，故數(shù)組 p 后面的值根據(jù)前面的值得來，這個思路沒有問題。

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

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

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

先從最簡單的情況開始：

1、當 id < i < mx 的時候，此時 id 之前的 p 值都已經(jīng)計算出來了，我們利用已經(jīng)計算出來的 p 值來計算當前位置的 p 值。

由于以 j 為中心的最長子回文串，落在了以 id 為中心的最長子回文串內(nèi)，由于 i 和 j 對稱， 故索引 i 附近的回文串可以與索引 j 附近的回文串建立一一對應的關系。

• 如果 j 的回文串很短，在 mx 關于 id 的對稱點之前結(jié)束，一定有 dp[i]=dp[j]，如上圖所示；
• 如果 j 的回文串很長，此時 dp[i] 的值不會超過 i 與 mx 之間的距離： mx - i，此時想一下 mx 是 以 id 為中心的最長回文子串的“最右邊界”，就不難理解了，如下圖所示 。

如果 p[j] 很大的話，即當 p[j] >= mx - i 的時候，以 s[j] 為中心的回文子串不一定完全包含于以 s[id] 為中心的回文子串中，但是基于對稱性可知，以 s[i] 為中心的回文子串，其向右至少會擴張到 mx 的位置，也就是說 p[i] >= mx - i。至于 mx 之后的部分是否對稱，就只能老老實實去匹配了。

image.png

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

把上面說的整理一下，當 p[j] 的范圍很小的時候，有 p[i] = p[j]，p[i] 的值再大不過超過 mx - i ：

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

2、當 i >= mx 的時候，此時也只能老老實實使用“中心擴散法”來逐漸得到 p 數(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ù)錯誤，您傳遞的分割字符，在輸入字符串中存在！");
        }
        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 算法的關鍵所在，一定要結(jié)合圖形來理解
                // 這一行代碼是關鍵，可以把兩種分類討論的情況合并
                p[i] = Integer.min(p[2 * id - i], mx - i);
            } else {
                // 走到這里，只可能是因為 i = mx
                if (i > mx) {
                    throw new IllegalArgumentException("程序出錯！");
                }
                p[i] = 1;
            }
            // 老老實實去匹配，看新的字符
            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 的值越大，
            // 進入上面 i < mx 的判斷的可能性就越大，這樣就可以重復利用之前判斷過的回文信息了
            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;
    }
}

復雜度分析：

• 時間復雜度：，由于 Manacher 算法只有在遇到還未匹配的位置時才進行匹配，已經(jīng)匹配過的位置不再匹配，所以對于對于字符串S 的每一個位置，都只進行一次匹配，所以算法的總體復雜度為 。
• 空間復雜度：。