題目描述
給定一個字符串 s，找到 s 中最長的迴文子串。你可以假設 s 長度最長為1000。
示例:
輸入: "babad"輸出: "bab"注意: "aba" 也是有效答案
示例:
輸入: "cbbd"輸出: "bb"
問題分析
最長迴文子串是一道非常經典的題，常見有暴力枚舉、動態規劃和 Mancher's Algorithm 這幾種解法，下面將一一詳細分析。
解決思路 1 —— 暴力枚舉法
暴力枚舉法是這幾種方法中最直觀的求解，求解過程中分別以每個元素為中間元素（奇數為最中間的一個數，偶數為中間元素的其中一個），同時從左右出發，計算出最長的迴文子串。
代碼實現
複雜度分析
時間複雜度：最外層循環複雜度為 O(n) ，內層兩個循環的複雜度都為 O(n/2) ，因此時間複雜度為 O(n2) 。
空間複雜度：在此算法中，沒有使用額外的輔助空間，因此空間複雜度為 O(1) 。
解決思路 2 —— 記憶化搜索
迴文字符串的子串也是迴文，我們可以將最長迴文子串分解一系列子問題，使用動態規劃求解。設狀態 f(i,j) 表示區間 [i,j] 是否為迴文串，f(i,j) = false 表示子串 [i,j] 不是迴文，f(i,j) = true 表示子串 [i,j] 是迴文串，則有以下的關係：
代碼實現
複雜度分析
時間複雜度：使用了兩層循環,因此時間複雜度為 O(n2) 。
空間複雜度：使用了 f[n][n] 作為輔助空間，因此空間複雜度為 O(n2) 。
解決思路 3 —— Mancher's Algorithm
Mancher 算法能夠很快的得到一個字符串中以任意一個字符為中心的迴文子串，其基本原理使用已知迴文串的左半部分來推導有半部分。
我們使用 rad[i] 表示以第i個字符為中心的最長迴文半徑，假設我們求出了 rad[0,...,i-1] 的值，現在我們需要通過已知的結果計算出 rad[i] 的值，在此我們定義 maxRight 是i位置前所有迴文串能延伸到的最右端位置，並且此時迴文串的中心位置為 k（取第一個達到最右端的位置），則我們可以得到 maxRight = k + rad[k] (中心位置加上半徑)，可以有以下兩種情況：
第一種情況：位置 i 不在前面的任何迴文串中，即 i > maxRight ，這時則初始化 rad[i] = 1 ，然後 rad[i] 向兩邊延伸，即
while(s[i+rad[i]] == s[i-rad[i]]) rad[i]++;
第二種情況：i 這個位置被前面位置 k 為中心的迴文串包含，即 i <= maxRight ，這種情況下 rad[i] 就不是從1開始。由迴文串的性質，我們可以知道 2k-i 這個位置與 i 關於 k 對稱，在這種情況下由可分為三種情形：
第一種情形：以 2k-i 為中心的迴文串有一部分在以i為中心迴文串之外，這種情況下rad[i]=maxRight-i=k+rad[k]-i,即為圖中空心箭頭長度，那有沒有可能rad[i]會更長呢？不可能，如果rad[i]會更長，則會延伸到k為中心的子串外，由於i和2k-i的對稱性可得到k為中心的子串會大於圖中紫色對應的半徑，與已知矛盾。
第二種情形：以 2k-i 為中心的迴文串在以i為中心迴文串之內，此時 rad[i] = rad[2k-i] ，那麼這個時候 rad[i] 會更長嗎？不可能，如果 rad[i] 長度更長，則延伸部分與 2k-i 正好對稱，這個時候 2k-i 子串半徑則大於圖中藍色箭頭的長度，矛盾。
第三種情形：以 2k-i 為中心的迴文串與 i 為中心迴文串左端部重疊，則 ran[i] = rad[2k-i] ，並且 rad[i] 可能繼續增加，所以有:
rad[i]=rad[2k-i];while(s[i+rad[i]] == s[i-rad[i]]) rad[i]++;
上面的方法存在一個問題，就是隻能計算出奇數長度的迴文子串，偶數的就不行，怎麼解決呢？這裡使用一個比較好的方法，在原來的串中每兩個字符之間添加一個特殊字符，如 aabbaca 變成 ^#a#a#b#b#a#c#a#$ ，這裡^$作為字符串的定界符是為了防止算法越界。這樣處理後，無論原來的迴文子串長度是偶數還是奇數，現在都變成奇數了。
代碼實現
複雜度分析
時間複雜度：Mancher 算法時間複雜度為 O(n) 。
空間複雜度：空間複雜度也為 O(n) 。
閱讀更多 領釦網 的文章
