??今天在lintCode做了一道面試題当悔，非常的簡單傅瞻，利用常規(guī)的方法計算起來非常的簡答踢代，但是有意思的就是挑戰(zhàn)項(xiàng)。我們先來看看題：
題意：
給出一個字符串（假設(shè)長度最長為1000）嗅骄，求出它的最長回文子串胳挎，你可以假
定只有一個滿足條件的最長回文串。
樣例：
給出字符串 "abcdzdcab"溺森，它的最長回文子串為 "cdzdc"慕爬。
挑戰(zhàn)：
O(n2) 時間復(fù)雜度的算法是可以接受的，如果你能用 O(n) 的算法那自然更好
??常規(guī)的方法在這里就不展示屏积，這里最主要的是展示Manacher算法医窿。
1.Manacher算法
??首先說明一下，Manacher算法能夠使得在O(n)的時間復(fù)雜度下找到最長的回文子串炊林。
(1).Manacher算法的概述
??Manacher算法只能解決長度為奇數(shù)的字符串姥卢，所以Manacher算法利用了一個比較巧妙的方法來同時解決長度為奇數(shù)或者偶數(shù)的字符串。Manacher算法通過轉(zhuǎn)換字符串來實(shí)現(xiàn)的渣聚，例如：原來的字符串：abc独榴，經(jīng)過轉(zhuǎn)換得到：#a#b#c#，這樣原來的字符串長度不管是奇數(shù)還是偶數(shù)奕枝，最終轉(zhuǎn)換都能夠得到一個長度為奇數(shù)的字符串棺榔。
??其次，Manacher算法通常還需要一個數(shù)組(我們假設(shè)是倍权，len數(shù)組)來記錄每一個字符在原字符串中的回文字符串的最大長度掷豺，其實(shí)實(shí)際上是，該字符在原來的字符串中得到的最長回文字符串的一半長度薄声。
??例如：aba当船，經(jīng)過轉(zhuǎn)換得到：#a#b#a#，b能得到的最長回文字符串是：#a#b#a#默辨，我們假設(shè)b的下標(biāo)是i德频，得到的最長字符串的第一個字符下標(biāo)是left，最后一個字符的下標(biāo)是right那么b對應(yīng)的值是：right - i + 1缩幸；
??同時壹置，我們還能知道的是，i對應(yīng)的字符得到的最大回文子串長度是：len[i] - 1,例如：上面的例子表谊，b的下標(biāo)是3钞护，所以len[3] = 4,那么b對應(yīng)的回文字符串a(chǎn)ba，長度恰好是len[3] - 1 = 3爆办。這個是為什么呢难咕？我們假設(shè)原來的字符串為oldString(沒有經(jīng)過轉(zhuǎn)換的)，轉(zhuǎn)換過后的字符串為newString，假設(shè)oldString長度為length余佃，那么newString的長度就為2 * length + 1,所以得到的字符串長度肯定為奇數(shù)暮刃。對于newString中的第i個字符對應(yīng)的回文字符串，長度肯定為2 * len[i] - 1(這個你們可以簡單的去舉例子測試一下)爆土，同時椭懊，經(jīng)過觀察得知，2 * len[i] - 1個字符中步势，肯定有l(wèi)en[i]個是#,其余的才是正常的符號氧猬，因?yàn)樵谒械幕匚淖址?的個數(shù)總是與其他符號的個數(shù)相差為1。
(2).len數(shù)組的計算
??首先立润，我們從左往右計算len[i]狂窑，當(dāng)我們計算len[i]時，len[j]已經(jīng)計算完畢(0 < j < i)桑腮。
??我們假設(shè)，在已經(jīng)計算了的字符當(dāng)中取得最長回文子串的右端點(diǎn)的最大值(該回文字符串不一定是最長的回文字符串蛉幸，只是要求該回文字符串右端下標(biāo)最大)破讨，假設(shè)最大值為rightIndex，并且設(shè)置該回文子串中心的位置是centerIndex奕纫，那么分為兩種情況：
??A.i < rightIndex
??我們假設(shè)以centerIndex為中心提陶，與i對應(yīng)的是j。如圖:
??我們知道的是匹层，以centerIndex為中心隙笆，回文字符串能達(dá)到rightIndex，那么此時有分為兩種情況：
??如果i + len[j] < P,也就是說升筏，以j為中心的回文字符串在以centerInde為中心的回文字符串內(nèi)部撑柔，此時可以得到以j為中心的回文字符串與以i為中心的回文字符串是相同的，為什么呢您访？因?yàn)樗麄冊谝詂enterIndex為中心的回文字符串的內(nèi)部铅忿。所以可以得到的是，len[i] = len[j]灵汪。
??如果i + len[j] >= P的話檀训，也就是說，以i為中心的回文字符串有一部分在以centerIndex為中心的回文字符串的外部享言，此時外部這一部分需要我們一個一個的計算峻凫。
??B.i > rightIndex
??如果i > rightIndex的話，那就說明览露，以i為中心的回文字符串一點(diǎn)都沒有匹配荧琼。所以需要我們一個一個的匹配了。
2.代碼
public static String longestPalindrome(String string) {
//-----------------------------------
//轉(zhuǎn)換字符串
StringBuilder stringBuilder = new StringBuilder();
stringBuilder.append("#");
for (int i = 0; i < string.length(); i++) {
stringBuilder.append(string.charAt(i));
stringBuilder.append("#");
}
//-----------------------------------
int rightIndex = 0;
int centerIndex = 0;
//求len中的最大
int answer = 0;
//answer最大時的中心
int index = 0;
int len[] = new int[stringBuilder.length() ];
for (int i = 1; i < stringBuilder.length(); i++) {
//當(dāng)rightIndex > i，那么我們就在rightIndex - i 與len[2 * centerIndex - i](len[j])铭腕，取得最小值
//因?yàn)楫?dāng)i + len[j] < rightIndex時银择，我們就把len[i]更新為len[j]
//但是如果i + len[j] >= rightIndex時，我們暫且將len[i]定更新為rightIndex - i,超出的部分需要我們一個一個的匹配
if (rightIndex > i) {
len[i] = Math.min(rightIndex - i, len[2 * centerIndex - i]);
} else {
len[i] = 1;
}
//一個一個匹配
//要么是超出的部分累舷，要么是i > rightIndex
while(i - len[i] >= 0 && i + len[i] < stringBuilder.length() && stringBuilder.charAt(i - len[i]) == stringBuilder.charAt(i + len[i])) {
len[i]++;
}
//當(dāng) len[i] + i > rightIndex,我們需要更新centerIndex和rightIndex
//至于為什么會這樣做浩考，理解一下rightIndex和centerIndex的含義
if(len[i] + i > rightIndex) {
rightIndex = len[i] + i;
centerIndex = i;
}
if(len[i] > answer) {
answer = len[i];
index = i;
}
}
//截取字符串
//為什么index - answer + 1,因?yàn)閘en[i] - 1才是原來的回文字符串長度，而answer記錄的是len中最大值
return stringBuilder.substring(index - answer + 1, index + answer).replace("#", "");
}
