題目來自lintcode, 鏈接：http://www.lintcode.com/zh-cn/problem/longest-palindromic-substring/
最長回文子串?
給出一個字符串（假設長度最長為1000），求出它的最長回文子串，你可以假定只有一個滿足條件的最長回文串。
樣例
給出字符串?"abcdzdcab"，它的最長回文子串為?"cdzdc"。
挑戰
O(n2) 時間復雜度的算法是可以接受的，如果你能用 O(n) 的算法那自然更好。
?
一. 首先給出O(n^2)的算法
思路：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]的最大值，最后找到最長回文子串的區間。
int dp[1005][1005];string longestPalindrome(string& s) {// Write your code hereO(n^2)int len = s.size();memset(dp, 0, sizeof(dp));for(int i=0; i<len; ++i)dp[i][1] = 1;int ld=0, rd=0, maxL = 1;for(int k=2; k<=len; ++k){for(int i=0, j; i<len && (j=i+k-1)<len; ++i){if(s[i] == s[j] && dp[i+1][k-2] == k-2)dp[i][k] = dp[i+1][k-2] + 2;else dp[i][k] = max(dp[i+1][k-1], dp[i][k-1]);if(maxL<dp[i][k]){maxL = dp[i][k];ld = i;rd = j;}}}return s.substr(ld, rd-ld+1);
}
二.然后看一下復雜度為O(n)的Manacher算法
2.1 先說一下這個算法的思想：
用一個數組 P[i] 來記錄以字符S[i]為中心的最長回文子串向左/右擴張的長度（包括S[i]）。
2.2 算法基本要點：
這個算法不能求出最長回文串長度為偶數回文串。用一個非常巧妙的方式，將所有可能的奇數/偶數長度的回文子串都轉換成了奇數長度：在相鄰兩個字符之間插入一個特殊的符號。比如 abba 變成 a#b#b#a。 為了進一步減少編碼的復雜度，可以在字符串的開始加入另一個特殊字符，這樣就不用特殊處理越界問題，比如$a#b#b#a。
2.3 具體說一個例子：
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正好是原字符串中回文串的總長度）
2.4 為啥要對字符串進行處理（插入'#'）
如果不對字符進行處理, 對于最長回文串為偶數的情況下：
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
可見不對字符進行處理，對于最長回文串為偶數的情況是不能得到最大的回文串的長度。
2.5 如何計算P數組的值:
算法增加兩個輔助變量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，然后再去匹配了。
2.6 尋找最大長度的回文子串：
看一種情況：
S[] ? ? 1 ?# ?2 ?# ?2 ?
P[] ? ? 1 ?1 ? 2 ?2 ?1?
首先， P中的最大值為2，但是最大值有兩個，我們應該選擇哪一個？其實，如果P中的最大值對應的字符不是'#'，顯然不能得到最大長度的回文串。所以當我們遇到這種情況時(maxP == P[i] && S[i]=='#')要更新最大值所在位置。
2.7 最后代碼：
class Solution { public:/*** @param s input string* @return the longest palindromic substring*/string manacher(string& str){int *p = new int[str.size()]();memset(p, 0, sizeof(p));int mx = 0, id = 0;for(int i=1; i<str.size(); i++){if(mx > i)p[i] = min(p[2*id-i], mx-i);elsep[i] = 1;while(str[i - p[i]] == str[i + p[i]])++p[i];if(i + p[i] > mx){mx = i + p[i];id = i;}}//尋找數組P中的最大值的位置int maxP = 0;for(int i=1; i<str.size(); ++i)if(maxP < p[i] || (maxP == p[i] && str[i]=='#')){maxP = p[i];id = i;} //根據id，確定最長回文串的區間int ld = id-p[id]+1, rd = id+p[id]-1;string ans = "";for(int i=ld; i<=rd; ++i)if(str[i]!='#')ans += str[i];return ans;}string longestPalindrome(string& s) {// Write your code here//采用manacher算法，O(n)的時間復雜度int len = s.size();
//首先預處理字符串，每兩個字符之間插入'#'int k = -1;for(int i=1; i<len; ++i)s.insert(k+=2, 1, '#');s.insert(0, 1, '$');return manacher(s);} };
?
