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

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

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

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

維基百科中對于“最長回文子串”介紹如下溪厘。

在計(jì)算機(jī)科學(xué)中，最長回文子串或最長對稱因子問題是在一個(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)”滿足“中心對稱”拆融，偶數(shù)回文串關(guān)于它“中間的兩個(gè)點(diǎn)”滿足“中心對稱”。
我們在具體判定一個(gè)字符串是否是回文串的時(shí)候啊终，常常會不自覺地考慮到它們之間的這個(gè)小的差別镜豹。

思路1：暴力匹配 Brute Force。

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

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

設(shè)計(jì)一個(gè)方法：傳入兩個(gè)索引編號參數(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：動態(tài)規(guī)劃。

有了計(jì)算機(jī)的幫助灾炭，解決這類“最優(yōu)子結(jié)構(gòu)”問題章鲤，當(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 (不能取等號，取到等號掏愁，就退化成 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 算法

維基百科中對于 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)”滿足“中心對稱”撒会，偶數(shù)回文串關(guān)于它“中間的兩個(gè)點(diǎn)”滿足“中心對稱”。我們在具體判定一個(gè)字符串是否是回文串的時(shí)候师妙，常常會不自覺地考慮到它們之間的這個(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ù)討論，對于使用“中心擴(kuò)散法”判定回文串的時(shí)候吓歇，長度為奇數(shù)和偶數(shù)的判定是不同的孽水，添加分隔符可以避免對奇偶性的討論。

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

首先城看，我們先來看一下如何填表女气。以字符串 "abbabb" 為例，說明如何手動計(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ù)組就是待檢測字符串加上分隔符以后的字符構(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ù)組很簡單了，把 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 的對稱索引婿滓。

我們通過分類討論，就可以得到這個(gè)等式粥喜。一開始凸主，我們是不能偷懶的，老老實(shí)實(shí)使用中心擴(kuò)散法來逐漸得到 p 數(shù)組的值额湘，同時(shí)記錄 id 和 mx卿吐。當(dāng)我們要考察的索引 i 超過了 mx 的時(shí)候，如下圖锋华，我們就可以偷點(diǎn)懶了嗡官。根據(jù)回文串的特點(diǎn)，i 關(guān)于 mx 的對稱點(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 的對稱點(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 的對稱點(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 對稱，以 s[i] 為中心的回文子串必然包含在以 s[id] 為中心的回文子串中记劝，所以必有 p[i] = p[j]变姨，見下圖。

Manacher 算法-2
Manacher 算法-3

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

Manacher 算法-4

4托嚣、對于 mx <= i 的情況巩检，無法對 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;
    }
}

參考資料

Manacher's Algorithm 馬拉車算法 - Grandyang - 博客園

https://www.cnblogs.com/grandyang/p/4475985.html

【看這篇文章就可以看懂】

Manacher算法總結(jié) - CSDN博客 https://blog.csdn.net/dyx404514/article/details/42061017

最長回文子串——Manacher 算法 - 曾會玩 - SegmentFault 思否 https://segmentfault.com/a/1190000003914228#articleHeader7

Manacher算法及其Java實(shí)現(xiàn) - CSDN博客 https://blog.csdn.net/simaxiaochen/article/details/62043408

參考資料：https://blog.csdn.net/hk2291976/article/details/51107886

1微驶、https://subetter.com/articles/2018/03/manacher-algorithm.html（這篇文章的圖最好了浪谴，把關(guān)鍵的部分和 代碼都給出來了）

2、https://blog.csdn.net/xingyeyongheng/article/details/9310555

3因苹、https://zhuhongcheng.wordpress.com/2009/08/02/a-simple-linear-time-algorithm-for-finding-longest-palindrome-sub-string/

4苟耻、https://blog.csdn.net/xingyeyongheng/article/details/9310555

介紹算法有圖。

5容燕、動態(tài)規(guī)劃的做法：

https://www.geeksforgeeks.org/longest-palindrome-substring-set-1/

6梁呈、也有圖和 Python 代碼

https://segmentfault.com/a/1190000003914228

https://segmentfault.com/a/1190000003914228

https://zh.wikipedia.org/wiki/%E6%9C%80%E9%95%BF%E5%9B%9E%E6%96%87%E5%AD%90%E4%B8%B2

（本節(jié)完）

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 人面猴
    序言：七十年代末，一起剝皮案震驚了整個(gè)濱河市蘸秘，隨后出現(xiàn)的幾起案子官卡，更是在濱河造成了極大的恐慌，老刑警劉巖醋虏，帶你破解...
    沈念sama閱讀 219,039評論 6贊 508
  • 死咒
    序言：濱河連續(xù)發(fā)生了三起死亡事件寻咒，死亡現(xiàn)場離奇詭異，居然都是意外死亡颈嚼，警方通過查閱死者的電腦和手機(jī)毛秘，發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 93,426評論 3贊 395
  • 救了他兩次的神仙讓他今天三更去死
    文/潘曉璐 我一進(jìn)店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來阻课，“玉大人叫挟，你說我怎么就攤上這事∠奚罚” “怎么了抹恳？”我有些...
    開封第一講書人閱讀 165,417評論 0贊 356
  • 道士緝兇錄：失蹤的賣姜人
    文/不壞的土叔 我叫張陵，是天一觀的道長署驻。 經(jīng)常有香客問我奋献，道長，這世上最難降的妖魔是什么旺上？ 我笑而不...
    開封第一講書人閱讀 58,868評論 1贊 295
  • ?港島之戀（遺憾婚禮）
    正文 為了忘掉前任瓶蚂，我火速辦了婚禮，結(jié)果婚禮上宣吱，老公的妹妹穿的比我還像新娘窃这。我一直安慰自己，他們只是感情好征候，可當(dāng)我...
    茶點(diǎn)故事閱讀 67,892評論 6贊 392
  • 惡毒庶女頂嫁案：這布局不是一般人想出來的
    文/花漫 我一把揭開白布杭攻。 她就那樣靜靜地躺著洒试，像睡著了一般。 火紅的嫁衣襯著肌膚如雪朴上。 梳的紋絲不亂的頭發(fā)上垒棋，一...
    開封第一講書人閱讀 51,692評論 1贊 305
  • 城市分裂傳說
    那天，我揣著相機(jī)與錄音痪宰，去河邊找鬼叼架。 笑死，一個(gè)胖子當(dāng)著我的面吹牛衣撬，可吹牛的內(nèi)容都是我干的乖订。 我是一名探鬼主播，決...
    沈念sama閱讀 40,416評論 3贊 419
  • 雙鴛鴦連環(huán)套：你想象不到人心有多黑
    文/蒼蘭香墨 我猛地睜開眼具练，長吁一口氣：“原來是場噩夢啊……” “哼乍构！你這毒婦竟也來了？” 一聲冷哼從身側(cè)響起扛点，我...
    開封第一講書人閱讀 39,326評論 0贊 276
  • 萬榮殺人案實(shí)錄
    序言：老撾萬榮一對情侶失蹤哥遮，失蹤者是張志新（化名）和其女友劉穎，沒想到半個(gè)月后陵究，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體眠饮，經(jīng)...
    沈念sama閱讀 45,782評論 1贊 316
  • ?護(hù)林員之死
    正文 獨(dú)居荒郊野嶺守林人離奇死亡，尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 37,957評論 3贊 337
  • ?白月光啟示錄
    正文 我和宋清朗相戀三年铜邮，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了仪召。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 40,102評論 1贊 350
  • 活死人
    序言：一個(gè)原本活蹦亂跳的男人離奇死亡松蒜，死狀恐怖扔茅，靈堂內(nèi)的尸體忽然破棺而出，到底是詐尸還是另有隱情秸苗，我是刑警寧澤召娜，帶...
    沈念sama閱讀 35,790評論 5贊 346
  • ?日本核電站爆炸內(nèi)幕
    正文 年R本政府宣布，位于F島的核電站难述，受9級特大地震影響萤晴，放射性物質(zhì)發(fā)生泄漏吐句。R本人自食惡果不足惜胁后，卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,442評論 3贊 331
  • 男人毒藥：我在死后第九天來索命
    文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望嗦枢。 院中可真熱鬧攀芯，春花似錦、人聲如沸文虏。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,996評論 0贊 22
  • 一樁弒父案殖演，背后竟有這般陰謀
    文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至年鸳，卻和暖如春趴久，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背搔确。 一陣腳步聲響...
    開封第一講書人閱讀 33,113評論 1贊 272
  • 情欲美人皮
    我被黑心中介騙來泰國打工彼棍， 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留，地道東北人膳算。 一個(gè)月前我還...
    沈念sama閱讀 48,332評論 3贊 373
  • 代替公主和親
    正文 我出身青樓座硕，卻偏偏與公主長得像，于是被迫代替她去往敵國和親涕蜂。 傳聞我的和親對象是個(gè)殘疾皇子华匾，可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,044評論 2贊 355