給出一個字元串（假設長度最長為1000），求出它的最長回文子串，你可以假定隻有一個滿足條件的最長回文串。
給出字元串 <code>"abcdzdcab"</code>，它的最長回文子串為 <code>"cdzdc"</code>。
o(n2) 時間複雜度的算法是可以接受的，如果你能用 o(n) 的算法那自然更好。
思路：dp[i][k]表示第i個位置開始長度為k的串的最大回文串的長度, j=i+k-1
當 s[i] == s[j] && dp[i+1][k-2] == k-2, dp[i][k] = dp[i+1][k-2] + 2;
否則 dp[i][k] = max(dp[i+1][k-1], dp[i][k-1]);
并記錄dp[i][k]的最大值，最後找到最長回文子串的區間。
用一個數組 p[i] 來記錄以字元s[i]為中心的最長回文子串向左/右擴張的長度（包括s[i]）。
這個算法不能求出最長回文串長度為偶數回文串。用一個非常巧妙的方式，将所有可能的奇數/偶數長度的回文子串都轉換成了奇數長度：在相鄰兩個字元之間插入一個特殊的符号。比如 abba 變成 a#b#b#a。 為了進一步減少編碼的複雜度，可以在字元串的開始加入另一個特殊字元，這樣就不用特殊處理越界問題，比如$a#b#b#a。
s[] 1 # 2 # 2 # 1 # 2 # 3 # 2 # 1
p[] 1 1 2 1 2 1 4 1 2 1 5 1 2 1 1
(p.s. 可以看出，p[i]-1正好是原字元串中回文串的總長度）
如果不對字元進行處理, 對于最長回文串為偶數的情況下：
s[] 1 2 1 1 2 1
p[] 1 2 1 1 2 1
對字元進行處理，對于最長回文串為偶數的情況下：
s[] 1 # 2 # 1 # 1 # 2 # 1
p[] 1 1 3 1 2 6 2 1 3 1 1
可見不對字元進行處理，對于最長回文串為偶數的情況是不能得到最大的回文串的長度。
算法增加兩個輔助變量id和mx，其中id表示最大回文子串中心的位置，mx則為id+p[id]，也就是最大回文子串的邊界。
當 mx - i > p[j] 的時候，以s[j]為中心的回文子串包含在以s[id]為中心的回文子串中，由于 i 和 j 對稱，以s[i]為中心的回文子串必然包含在以s[id]為中心的回文子串中，是以必有 p[i] = p[j]，見下圖。
當 p[j] > mx - i 的時候，以s[j]為中心的回文子串不完全包含于以s[id]為中心的回文子串中，但是基于對稱性可知，下圖中兩個綠框所包圍的部分是相同的，也就是說以s[i]為中心的回文子串，其向右至少會擴張到mx的位置，也就是說 p[i] >= mx - i。至于mx之後的部分是否對稱，就隻能一個一個比對了。
對于 mx <= i 的情況，無法對 p[i]做更多的假設，隻能p[i] = 1，然後再去比對了。
看一種情況：
s[] 1 # 2 # 2
p[] 1 1 2 2 1
首先， p中的最大值為2，但是最大值有兩個，我們應該選擇哪一個？其實，如果p中的最大值對應的字元不是'#'，顯然不能得到最大長度的回文串。是以當我們遇到這種情況時(maxp == p[i] && s[i]=='#')要更新最大值所在位置。