leetcode地址：5. 最長回文子串

解答參考：動態規劃、中心擴散、Manacher 算法

問題描述：

給你一個字符串?s，找到?s?中最長的回文子串。比如給定字符串s = "babad" ，找出最長的回文子串為"bab"

算法思路：

本題可以采用暴力破解法、中心擴散法、Manacher算法3種方法，本篇文章講解Manacher。Manacher 算法，被中國程序員戲稱為“馬拉車”算法。它專門用于解決“最長回文子串”問題，時間復雜度為 O(N)。維基百科中對于 Manacher 算法是這樣描述的：

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

Manacher 算法本質上還是中心擴散法，只不過它使用了類似 KMP 算法的技巧，充分挖掘了已經進行回文判定的子串的特點，在遍歷的過程中，記錄了已經遍歷過的子串的信息，也是典型的以空間換時間思想的體現。

下面介紹 Manacher 算法的具體流程。

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

首先在字符串的首尾、相鄰的字符中插入分隔符，例如 "babad" 添加分隔符 "#" 以后得到 "#b#a#b#a#d#"。對這一點有如下說明：

分隔符是一個字符，種類也只有一個，并且這個字符一定不能是原始字符串中出現過的字符；

加入了分隔符以后，使得“間隙”有了具體的位置，方便后續的討論，并且新字符串中的任意一個回文子串在原始字符串中的一定能找到唯一的一個回文子串與之對應，因此對新字符串的回文子串的研究就能得到原始字符串的回文子串；

新字符串的回文子串的長度一定是奇數；

新字符串的回文子串一定以分隔符作為兩邊的邊界，因此分隔符起到“哨兵”的作用。

第 2 步：計算輔助數組 p

輔助數組 p 記錄了新字符串中以每個字符為中心的回文子串的信息。手動的計算方法仍然是“中心擴散法”，此時記錄以當前字符為中心，向左右兩邊同時擴散，記錄能夠擴散的最大步數。以字符串 "abbabb" 為例，說明如何手動計算得到輔助數組 p ，我們要填的就是下面這張表。

• 第 1 行數組 char ：原始字符串加上分隔符以后的每個字符。
• 第 2 行數組 index ：這個數組是新字符串的索引數組，它的值是從 0開始的索引編號。

• p[0]：以 char[0] = '#' 為中心，同時向左邊向右擴散，走 1 步就碰到邊界了，因此能擴散的步數為 0，因此 p[0] = 0；? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
• p[1]：以 char[1] = 'a' 為中心，同時向左邊向右擴散，走 1?步，左右都是 "#"，構成回文子串，于是再繼續同時向左邊向右邊擴散，左邊就碰到邊界了，最多能擴散的步數”為 1，因此 p[1] = 1；
• p[2]：以 char[2] = '#' 為中心，同時向左邊向右擴散，走 1 步，左邊是 "a"，右邊是 "b"，不匹配，最多能擴散的步數為 0，因此 p[2] = 0；
• p[3]：以 char[3] = 'b' 為中心，同時向左邊向右擴散，走 1?步，左右兩邊都是 “#”，構成回文子串，繼續同時向左邊向右擴散，左邊是 "a"，右邊是 "b"，不匹配，最多能擴散的步數為 1?，因此 p[3] = 1；? ? ? ? ? ? ? ? ? ? ? ? ? ?
• p[4]：以 char[4] = '#' 為中心，同時向左邊向右擴散，最多可以走 4?步，左邊到達左邊界，因此 p[4] = 4。? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
• 繼續填完 p 數組剩下的部分。

說明：有些資料將輔助數組 p 定義為回文半徑數組，即 p[i] 記錄了以新字符串第 i 個字符為中心的回文字符串的半徑（包括第 i 個字符），與我們這里定義的輔助數組 p 有一個字符的偏差，本質上是一樣的。下面是輔助數組 p 的結論：輔助數組 p 的最大值是 5，對應了原字符串 "abbabb" 的 “最長回文子串” ："bbabb"。這個結論具有一般性，即：

輔助數組 p 的最大值就是“最長回文子串”的長度。

因此，我們可以在計算輔助數組 p 的過程中記錄這個最大值，并且記錄最長回文子串。簡單說明一下這是為什么：

如果新回文子串的中心是一個字符，那么原始回文子串的中心也是一個字符，在新回文子串中，向兩邊擴散的特點是：“先分隔符，后字符”，同樣擴散的步數因為有分隔符 # 的作用，在新字符串中每擴散兩步，雖然實際上只掃到一個有效字符，但是相當于在原始字符串中相當于計算了兩個字符。因為最后一定以分隔符結尾，還要計算一個，正好這個就可以把原始回文子串的中心算進去；

如果新回文子串的中心是 #，那么原始回文子串的中心就是一個“空隙”。在新回文子串中，向兩邊擴散的特點是：“先字符，后分隔符”，擴散的步數因為有分隔符 # 的作用，在新字符串中每擴散兩步，雖然實際上只掃到一個有效字符，但是相當于在原始字符串中相當于計算了兩個字符。
因此，“輔助數組 p 的最大值就是“最長回文子串”的長度”這個結論是成立的，可以看下面的圖理解上面說的 2 點。

寫到這里，其實已經能寫出一版代碼，把這一版代碼提交到 LeetCode 是可以通過的，這同樣也可以驗證我們上面的結論是正確的。

public class Solution {public String longestPalindrome(String s) {int len = s.length();if (len < 2) {return s;}String str = addBoundaries(s, '#');int sLen = 2 * len + 1;int maxLen = 1;int start = 0;for (int i = 0; i < sLen; i++) {int curLen = centerSpread(str, i);if (curLen > maxLen) {maxLen = curLen;start = (i - maxLen) / 2;}}return s.substring(start, start + maxLen);}private int centerSpread(String s, int center) {int len = s.length();int i = center - 1;int j = center + 1;int step = 0;while (i >= 0 && j < len && s.charAt(i) == s.charAt(j)) {i--;j++;step++;}return step;}/*** 創建預處理字符串** @param s 原始字符串* @param divide 分隔字符* @return 使用分隔字符處理以后得到的字符串*/private String addBoundaries(String s, char divide) {int len = s.length();if (len == 0) {return "";}if (s.indexOf(divide) != -1) {throw new IllegalArgumentException("參數錯誤，您傳遞的分割字符，在輸入字符串中存在！");}StringBuilder stringBuilder = new StringBuilder();for (int i = 0; i < len; i++) {stringBuilder.append(divide);stringBuilder.append(s.charAt(i));}stringBuilder.append(divide);return stringBuilder.toString();} }

復雜度分析：

時間復雜度：O(N^2)，這里 NN 是原始字符串的長度。新字符串的長度是 2 \times N+ 12×N+1，不計系數與常數項，因此時間復雜度仍為 O(N^2)。

空間復雜度：O(N)O(N)。

科學家的工作：充分利用新字符串的回文性質，計算輔助數組 p。

上面的代碼不太智能的地方是，對新字符串每一個位置進行中心擴散，會導致原始字符串的每一個字符被訪問多次，一個比較極端的情況就是：#a#a#a#a#a#a#a#a#。事實上，計算機科學家 Manacher 就改進了這種算法，使得在填寫新的輔助數組 p 的值的時候，能夠參考已經填寫過的輔助數組 p 的值，使得新字符串每個字符只訪問了一次，整體時間復雜度由 O(N^2)改進到 O(N)。具體做法是：在遍歷的過程中，除了循環變量 i 以外，我們還需要記錄兩個變量，它們是 maxRight 和 center ，它們分別的含義如下：

maxRight：記錄當前向右擴展的最遠邊界，即從開始到現在使用“中心擴散法”能得到的回文子串，它能延伸到的最右端的位置 。對于 maxRight 我們說明 3 點：

“向右最遠”是在計算輔助數組 p 的過程中，向右邊擴散能走的索引最大的位置，注意：得到一個 maxRight 所對應的回文子串，并不一定是當前得到的“最長回文子串”，很可能的一種情況是，某個回文子串可能比較短，但是它正好在整個字符串比較靠后的位置；

maxRight 的下一個位置可能是被程序看到的，停止的原因有 2 點：（1）左邊界不能擴散，導致右邊界受限制也不能擴散，maxRight 的下一個位置看不到；（2）正是因為看到了 maxRight 的下一個位置，導致 maxRight 不能繼續擴散。

為什么 maxRight 很重要？因為掃描是從左向右進行的， maxRight 能夠提供的信息最多，它是一個重要的分類討論的標準，因此我們需要一個變量記錄它。

center：center 是與 maxRight 相關的一個變量，它是上述 maxRight 的回文中心的索引值。對于 center 的說明如下：

center 的形式化定義：center=argmax{x+p[x]∣0≤x<i}。：x + p[x] 的最大值就是我們定義的 maxRight，i 是循環變量，0<= x< i 表示是在 i 之前的所有索引里得到的最大值 maxRight，它對應的回文中心索引就是上述式子。

maxRight 與 center 是一一對應的關系，即一個 center 的值唯一對應了一個 maxRight 的值；因此 maxRight 與 center 必須要同時更新。

下面的討論就根據循環變量 i 與 maxRight 的關系展開討論：

情況 1：當 i >= maxRight 的時候，這就是一開始，以及剛剛把一個回文子串掃描完的情況，此時只能夠根據“中心擴散法”一個一個掃描，逐漸擴大 maxRight；

情況 2：當 i < maxRight 的時候，根據新字符的回文子串的性質，循環變量關于 center 對稱的那個索引（記為 mirror）的 p 值就很重要。我們先看 mirror 的值是多少，因為 center 是中心，i 和 mirror 關于 center 中心對稱，因此 (mirror + i) / 2 = center ，所以 mirror = 2 * center - i。根據 p[mirror] 的數值從小到大，具體可以分為如下 3 種情況：

情況 2（1）：p[mirror] 的數值比較小，不超過 maxRight - i。

說明：maxRight - i 的值，就是從 i 關于 center 的鏡像點開始向左走（不包括它自己），到 maxRight 關于 center 的鏡像點的步數。從圖上可以看出，由于“以 center 為中心的回文子串”的對稱性，導致了“以 i 為中心的回文子串”與“以 center 為中心的回文子串”也具有對稱性，“以 i 為中心的回文子串”與“以 center 為中心的回文子串”不能再擴散了，此時，直接把數值抄過來即可，即 p[i] = p[mirror]。

情況 2（2）：p[mirror] 的數值恰好等于 maxRight - i。

說明：仍然是依據“以 center 為中心的回文子串”的對稱性，導致了“以 i 為中心的回文子串”與“以 center 為中心的回文子串”也具有對稱性。因為靠左邊的 f 與靠右邊的 g 的原因，導致“以 center 為中心的回文子串”不能繼續擴散；但是“以 i 為中心的回文子串” 還可以繼續擴散。因此，可以先把 p[mirror] 的值抄過來，然后繼續“中心擴散法”，繼續增加 maxRight。

情況 2（3）：p[mirror] 的數值大于 maxRight - i。

說明：仍然是依據“以 center 為中心的回文子串”的對稱性，導致了“以 i 為中心的回文子串”與“以 center 為中心的回文子串”也具有對稱性。下面證明，p[i] = maxRight - i ，證明的方法還是利用三個回文子串的對稱性。

• ① 由于“以 center 為中心的回文子串”的對稱性， 黃色箭頭對應的字符 c 和 e 一定不相等；
• ② 由于“以 mirror 為中心的回文子串”的對稱性， 綠色箭頭對應的字符 c 和 c 一定相等；
• ③ 又由于“以 center 為中心的回文子串”的對稱性， 藍色箭頭對應的字符 c 和 c 一定相等；

推出“以 i 為中心的回文子串”的對稱性， 紅色箭頭對應的字符 c 和 e 一定不相等。因此，p[i] = maxRight - i，不可能再大。上面是因為我畫的圖，可能看的朋友會覺得理所當然。事實上，可以使用反證法證明：如果“以 i 為中心的回文子串” 再向兩邊擴散的兩個字符 c 和 e 相等，就能夠推出黃色、綠色、藍色、紅色箭頭所指向的 8 個變量的值都相等，此時“以 center 為中心的回文子串” 就可以再同時向左邊和右邊擴散 11 格，與 maxRight 的最大性矛盾。綜合以上 3 種情況，當 i < maxRight 的時候，p[i] 可以參考 p[mirror] 的信息，以 maxRight - i 作為參考標準，p[i] 的值應該是保守的，即二者之中較小的那個值：p[i] = min(maxRight - i, p[mirror]);

public class Solution {public String longestPalindrome(String s) {// 特判int len = s.length();if (len < 2) {return s;}// 得到預處理字符串String str = addBoundaries(s, '#');// 新字符串的長度int sLen = 2 * len + 1;// 數組 p 記錄了掃描過的回文子串的信息int[] p = new int[sLen];// 雙指針，它們是一一對應的，須同時更新int maxRight = 0;int center = 0;// 當前遍歷的中心最大擴散步數，其值等于原始字符串的最長回文子串的長度int maxLen = 1;// 原始字符串的最長回文子串的起始位置，與 maxLen 必須同時更新 int start = 0;for (int i = 0; i < sLen; i++) {if (i < maxRight) {int mirror = 2 * center - i;// 這一行代碼是 Manacher 算法的關鍵所在，要結合圖形來理解p[i] = Math.min(maxRight - i, p[mirror]);}// 下一次嘗試擴散的左右起點，能擴散的步數直接加到 p[i] 中int left = i - (1 + p[i]);int right = i + (1 + p[i]);// left >= 0 && right < sLen 保證不越界// str.charAt(left) == str.charAt(right) 表示可以擴散 1 次while (left >= 0 && right < sLen && str.charAt(left) == str.charAt(right)) {p[i]++;left--;right++;}// 根據 maxRight 的定義，它是遍歷過的 i 的 i + p[i] 的最大者// 如果 maxRight 的值越大，進入上面 i < maxRight 的判斷的可能性就越大，這樣就可以重復利用之前判斷過的回文信息了if (i + p[i] > maxRight) {// maxRight 和 center 需要同時更新maxRight = i + p[i];center = i;}if (p[i] > maxLen) {// 記錄最長回文子串的長度和相應它在原始字符串中的起點maxLen = p[i];start = (i - maxLen) / 2;}}return s.substring(start, start + maxLen);}/*** 創建預處理字符串** @param s 原始字符串* @param divide 分隔字符* @return 使用分隔字符處理以后得到的字符串*/private String addBoundaries(String s, char divide) {int len = s.length();if (len == 0) {return "";}if (s.indexOf(divide) != -1) {throw new IllegalArgumentException("參數錯誤，您傳遞的分割字符，在輸入字符串中存在！");}StringBuilder stringBuilder = new StringBuilder();for (int i = 0; i < len; i++) {stringBuilder.append(divide);stringBuilder.append(s.charAt(i));}stringBuilder.append(divide);return stringBuilder.toString();} }

復雜度分析：

時間復雜度：O(N)，Manacher 算法只有在遇到還未匹配的位置時才進行匹配，已經匹配過的位置不再匹配，因此對于字符串 S 的每一個位置，都只進行一次匹配，算法的復雜度為 O(N)。

空間復雜度：O(N)。

總結

以上是生活随笔為你收集整理的回文字符串—回文子串—Manacher算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。