文章出處

[譯+改]最長回文子串(Longest Palindromic Substring) Part II

原文鏈接在http://leetcode.com/2011/11/longest-palindromic-substring-part-ii.html

原文作者有些地方邏輯上有點小問題，我做了糾正。關于解釋時間復雜度上，原作者就只有兩句話，我無法理解，特意在此加強了，便于理解。

問題：給定字符串S，求S中的最長回文子串。

在上一篇，我們給出了4種算法，其中包括一個O(N²)時間O(1)空間的算法（中心檢測法），已經很不錯了。本篇將討論一個O(N)時間O(N)空間的算法，即著名的Manacher算法，并詳細說明其時間復雜度為何是O(N)。

提示

+BIT祝威+悄悄在此留下版了個權的信息說：

先想想有什么辦法能改進中心檢測法。

考慮一下最壞的情況。★

最壞的情況就是各個回文相互重疊的時候。例如"aaaaaaaaaa"和" cabcbabcbabcba"。

為什么說有重疊時是最壞的情況？因為會發生重復計算。★（換句話說，沒有重疊時，必須要一點一點計算，也就沒有可改進的余地了。）

花費一些空間來避免重復計算。★

利用回文的特性避免重復計算。★

一個O(N)的算法(Manacher)

+BIT祝威+悄悄在此留下版了個權的信息說：

首先我們把字符串S改造一下變成T，改造方法是：在S的每個字符之間和S首尾都插入一個"#"。這樣做的理由你很快就會知道。

例如，S="abaaba"，那么T="#a#b#a#a#b#a#"。

想一下，你必須在以Ti為中心左右擴展才能確定以Ti為中心的回文長度d到底是多少。（就是說這一步是無法避免的）

為了改進最壞的情況，我們把各個Ti處的回文半徑存儲到數組P，用P[i]表示以Ti為中心的回文長度。那么當我們求出所有的P[i]，取其中最大值就能找到最長回文子串了。

對于上文的示例，我們先直接寫出所有的P研究一下。

i = 0 1 2 3 4 5 6 7 8 9 A B C

T = # a # b # a # a # b # a #

P = 0 1 0 3 0 1 6 1 0 3 0 1 0

+BIT祝威+悄悄在此留下版了個權的信息說：

顯然最長子串就是以P[6]為中心的"abaaba"。

你是否發現了，在插入"#"后，長度為奇數和偶數的回文都可以優雅地處理了？這就是其用處。

現在，想象你在"abaaba"中心畫一道豎線，你是否注意到數組P圍繞此豎線是中心對稱的？再試試"aba"的中心，P圍繞此中心也是對稱的。這當然不是巧合，而是在某個條件下的必然規律。我們將利用此規律減少對數組P中某些元素的重復計算。

我們來看一個重疊得更典型的例子，即S="babcbabcbaccba"。

上圖展示了把S轉換為T的樣子。假設你已經算出了一部分P。豎實線表示回文"abcbabcba"的中心C，兩個虛實線表示其左右邊界L和R。你下一步要計算P[i]，i圍繞C的對稱點是i’。你有辦法高效地計算P[i]嗎？

我們先看一下i圍繞C的對稱點i’（此時i’=9）。

據上圖所示，很明顯P[i]=P[i’]=1。這是因為i和i’圍繞C對稱。同理，P[12]=P[10]=0，P[14]=P[8]=0。

現在再看i=15處。此時P[15]=P[7]=7？錯了，你逐個字符檢測一下會發現此時P[15]應該是5。

為什么此時規則變了？

如上圖所示，兩條綠色實線劃定的范圍必定是對稱的，兩條綠色虛線劃定的范圍必定也是對稱的。此時請注意P[i’]=7，超過了左邊界L。超出的部分就不對稱了。此時我們只知道P[i]>=5，至于P[i]還能否擴展，只有通過逐個字符檢測才能判定了。

在此例中，P[21]≠P[9]，所以P[i]=P[15]=5。

我們總結一下上述分析過程，就是這個算法的關鍵部分了。

if P[ i' ] < R – i,

then P[ i ] ← P[ i' ]

else P[ i ] ≥ R - i. (此時要穿過R逐個字符判定P[i]).

（注：原作者的寫法在邏輯上欠妥，我作了修正）

是不是很優雅？如果你能理解到這里，你已經搞定了這個算法最困難也最精華的部分了。

很明顯C的位置也是需要移動的，這個很容易：

如果i處的回文超過了R，那么就C=i，同時相應改變L和R即可。

+BIT祝威+悄悄在此留下版了個權的信息說：

每次求P[i]，都有兩種可能。如果P[i‘] < R – i，我們就P[i] = P[i’]。否則，就從R開始逐個字符求P[i]，并更新C及其R。此時擴展R（逐個字符求P[i]）最多用N步，而求每個C也總共需要N步。所以時間復雜度是2*N，即O(N)。

（注：原作者計算時間復雜度的這句話我沒看懂。我自己想辦法理解了，詳情見下圖。

圖中i為索引，T為加入"#"、"^"和"$"后的字符串，P[i]就是算法里的p[i]，calc[i]是為了求出P[i]而需要執行比較的次數。

"V"表示此列的字符與其左側的字符進行了比較，在左側用"X"對應。綠色的表示比較結果為兩個字符相同（即比較結果為成功），紅色的表示不同（即比較結果為失敗）。

很顯然"X"和"V"的數量是相等的。

你可以看到，所需的成功比較的次數（綠色的"V"，表現為橫向增長）不超過N，失敗的次數（紅色的"V"，表現為縱向增長）也不超過N，所以這個算法的時間復雜度就是2N，即O(N)。

）

原作者的程序不便于理解，我貼上我的代碼。

 1 public class Solution {
 2     // Transform S into T.
 3     // For example, S = "abba", T = "^#a#b#b#a#$".
 4     // ^ and $ signs are sentinels appended to each end to avoid bounds checking
 5     String preProcess(String s) {
 6         int n = s.length();
 7         if (n == 0) return "^$";
 8 
 9         String ret = "^";
10         for (int i = 0; i < n; i++)
11         {
12             ret += "#" + s.substring(i, i + 1);
13         }
14         
15         ret += "#$";
16         return ret;
17     }
18     public String longestPalindrome(String s) {
19         String T = preProcess(s);
20         int length = T.length();
21         int[] p = new int[length];
22         int C = 0, R = 0;
23         
24         for (int i = 1; i < length - 1; i++)
25         {
26             int i_mirror = C - (i - C);
27             int diff = R - i;
28             if (diff >= 0)//當前i在C和R之間，可以利用回文的對稱屬性
29             {
30                 if (p[i_mirror] < diff)//i的對稱點的回文長度在C的大回文范圍內部
31                 { p[i] = p[i_mirror]; }
32                 else
33                 {
34                     p[i] = diff;
35                     //i處的回文可能超出C的大回文范圍了
36                     while (T.charAt(i + p[i] + 1) == T.charAt(i - p[i] - 1))
37                     { p[i]++; }
38                     C = i;
39                     R = i + p[i];
40                 }
41             }
42             else
43             {
44                 p[i] = 0;
45                 while (T.charAt(i + p[i] + 1) == T.charAt(i - p[i] - 1))
46                 { p[i]++; }
47                 C = i;
48                 R = i + p[i];
49             }
50         }
51 
52         int maxLen = 0;
53         int centerIndex = 0;
54         for (int i = 1; i < length - 1; i++) {
55             if (p[i] > maxLen) {
56               maxLen = p[i];
57               centerIndex = i;
58             }
59         }
60         return s.substring((centerIndex - 1 - maxLen) / 2, (centerIndex - 1 - maxLen) / 2 + maxLen);        
61     }
62 }