轉(zhuǎn)載：https://segmentfault.com/a/1190000003914228
0. 問題定義
最長回文子串問題：給定一個字符串，求它的最長回文子串長度米苹。
如果一個字符串正著讀和反著讀是一樣的璧针，那它就是回文串雷恃。下面是一些回文串的實例：
12321 a aba abba aaaa tattarrattat（牛津英語詞典中最長的回文單詞）
1. Brute-force 解法
對于最長回文子串問題腹尖，最簡單粗暴的辦法是：找到字符串的所有子串抒巢，遍歷每一個子串以驗證它們是否為回文串胎撇。一個子串由子串的起點和終點確定介粘，因此對于一個長度為n的字符串，共有n2個子串晚树。這些子串的平均長度大約是n/2姻采，因此這個解法的時間復雜度是O(n3)。
2. 改進的方法
顯然所有的回文串都是對稱的爵憎。長度為奇數(shù)回文串以最中間字符的位置為對稱軸左右對稱慨亲，而長度為偶數(shù)的回文串的對稱軸在中間兩個字符之間的空隙”模可否利用這種對稱性來提高算法效率呢刑棵？答案是肯定的。我們知道整個字符串中的所有字符愚铡，以及字符間的空隙蛉签，都可能是某個回文子串的對稱軸位置∶剑可以遍歷這些位置正蛙，在每個位置上同時向左和向右擴展，直到左右兩邊的字符不同营曼，或者達到邊界乒验。對于一個長度為n的字符串，這樣的位置一共有n+n-1=2n-1個蒂阱，在每個位置上平均大約要進行n/4次字符比較锻全，于是此算法的時間復雜度是O(n^2)。
3. Manacher 算法
對于一個比較長的字符串录煤，O(n^2)的時間復雜度是難以接受的鳄厌。Can we do better?
先來看看解法2存在的缺陷。
- 由于回文串長度的奇偶性造成了不同性質(zhì)的對稱軸位置妈踊，解法2要對兩種情況分別處理了嚎；
- 很多子串被重復多次訪問，造成較差的時間效率廊营。
缺陷2）可以通過這個直觀的小?體現(xiàn)：
char: a b a b a
i : 0 1 2 3 4
當i==1歪泳，和i==2時，左邊的子串a(chǎn)ba分別被遍歷了一次露筒。
如果我們能改善解法2的不足呐伞，就很有希望能提高算法的效率。Manacher正是針對這些問題改進算法慎式。
(1) 解決長度奇偶性帶來的對稱軸位置問題
Manacher算法首先對字符串做一個預處理伶氢，在所有的空隙位置(包括首尾)插入同樣的符號趟径，要求這個符號是不會在原串中出現(xiàn)的。這樣會使得所有的串都是奇數(shù)長度的癣防。以插入#號為例：
aba ———> #a#b#a#
abba ———> #a#b#b#a#
插入的是同樣的符號蜗巧，且符號不存在于原串，因此子串的回文性不受影響劣砍，原來是回文的串惧蛹，插完之后還是回文的，原來不是回文的刑枝，依然不會是回文香嗓。
(2) 解決重復訪問的問題
我們把一個回文串中最左或最右位置的字符與其對稱軸的距離稱為回文半徑。Manacher定義了一個回文半徑數(shù)組RL装畅，用RL[i]表示以第i個字符為對稱軸的回文串的回文半徑靠娱。我們一般對字符串從左往右處理，因此這里定義RL[i]為第i個字符為對稱軸的回文串的最右一個字符與字符i的距離掠兄。對于上面插入分隔符之后的兩個串像云，可以得到RL數(shù)組：
char: # a # b # a #
RL : 1 2 1 4 1 2 1
RL-1: 0 1 0 3 0 1 0
i : 0 1 2 3 4 5 6
char: # a # b # b # a #
RL : 1 2 1 2 5 2 1 2 1
RL-1: 0 1 0 1 4 1 0 1 0
i : 0 1 2 3 4 5 6 7 8
上面我們還求了一下RL[i]-1。通過觀察可以發(fā)現(xiàn)蚂夕，RL[i]-1的值迅诬，正是在原本那個沒有插入過分隔符的串中，以位置i為對稱軸的最長回文串的長度婿牍。那么只要我們求出了RL數(shù)組侈贷，就能得到最長回文子串的長度。
于是問題變成了等脂，怎樣高效地求的RL數(shù)組俏蛮。基本思路是利用回文串的對稱性，擴展回文串上遥。
我們再引入一個輔助變量MaxRight搏屑，表示當前訪問到的所有回文子串，所能觸及的最右一個字符的位置粉楚。另外還要記錄下MaxRight對應的回文串的對稱軸所在的位置辣恋，記為pos，它們的位置關系如下模软。
[圖片上傳失敗...(image-8caaf9-1525833853509)]
我們從左往右地訪問字符串來求RL伟骨，假設當前訪問到的位置為i，即要求RL[i]撵摆，在對應上圖底靠，i必然是在po右邊的(obviously)害晦。但我們更關注的是特铝，i是在MaxRight的左邊還是右邊暑中。我們分情況來討論。
1）當i在MaxRight的左邊
情況1)可以用下圖來刻畫：
[圖片上傳失敗...(image-1bdb7c-1525833853509)]
我們知道鲫剿，圖中兩個紅色塊之間（包括紅色塊）的串是回文的鳄逾；并且以i為對稱軸的回文串，是與紅色塊間的回文串有所重疊的灵莲。我們找到i關于pos的對稱位置j雕凹，這個j對應的RL[j]我們是已經(jīng)算過的。根據(jù)回文串的對稱性政冻，以i為對稱軸的回文串和以j為對稱軸的回文串枚抵，有一部分是相同的。這里又有兩種細分的情況明场。
- 以
j為對稱軸的回文串比較短汽摹，短到像下圖這樣。
[圖片上傳失敗...(image-be0cda-1525833853509)]
這時我們知道RL[i]至少不會小于RL[j]苦锨，并且已經(jīng)知道了部分的以i為中心的回文串逼泣，于是可以令RL[i]=RL[j]。但是以i為對稱軸的回文串可能實際上更長舟舒，因此我們試著以i為對稱軸拉庶，繼續(xù)往左右兩邊擴展，直到左右兩邊字符不同秃励，或者到達邊界氏仗。
- 以
j為對稱軸的回文串很長，這么長：
[圖片上傳失敗...(image-a46b8c-1525833853509)]
這時莺治，我們只能確定廓鞠，兩條藍線之間的部分（即不超過MaxRight的部分）是回文的，于是從這個長度開始谣旁，嘗試以i為中心向左右兩邊擴展床佳，，直到左右兩邊字符不同榄审，或者到達邊界砌们。
不論以上哪種情況，之后都要嘗試更新MaxRight和pos搁进，因為有可能得到更大的MaxRight浪感。
具體操作如下：
step 1: 令RL[i]=min(RL[2*pos-i], MaxRight-i)
step 2: 以i為中心擴展回文串，直到左右兩邊字符不同饼问，或者到達邊界影兽。
step 3: 更新MaxRight和pos
2）當i在MaxRight的右邊
[圖片上傳失敗...(image-be0815-1525833853509)]
遇到這種情況，說明以i為對稱軸的回文串還沒有任何一個部分被訪問過莱革，于是只能從i的左右兩邊開始嘗試擴展了峻堰，當左右兩邊字符不同讹开，或者到達字符串邊界時停止。然后更新MaxRight和pos捐名。
思考：為什么輔助變量要選擇記錄“當前訪問到的所有回文子串所能觸及的最右一個字符的位置”旦万，而不是諸如“當前訪問到最長回文子串”。
這樣能夠憑借已經(jīng)遍歷的經(jīng)驗镶蹋，找到以i為對稱軸的較長子串成艘，子串長度以 maxRight 為界。也就是說贺归，能憑借經(jīng)驗得到的子串長度為 (maxRight-pos)*2+1淆两，當然 maxRight 越大直接得出的子串越長，就越省事啦拂酣。
(3) 算法實現(xiàn)
//代碼一：leetcode 時間較短的方案
class Solution {
private int start = 0;
private int maxLength = 1;
public String longestPalindrome(String s){
if (s.length() < 2)
return s;
for (int i = 0; i < s.length(); i++){
getMaxLength(s, i, i);
getMaxLength(s, i, i+1);
}
return s.substring(start, start+maxLength);
}
private void getMaxLength(String s, int i, int j){
while (i >= 0 && j < s.length() && s.charAt(i) == s.charAt(j)){
if (maxLength < (j-i+1)){
maxLength = j-i+1;
start = i;
}
i--;
j++;
}
}
}
//代碼二：我的解法
/**
* @Title: 最長回文子串
* @Description: 給定一個字符串s琼腔，找到s中最長的回文子串。你可以假設s的最大長度為1000踱葛。
*/
public String longestPalindrome(String s) {
//字符數(shù)組預處理,轉(zhuǎn)換偶數(shù)長度的回文子串
//如 abdcccs 轉(zhuǎn)換成 #a#b#d#c#c#c#s#
char[] chars = pretreatmentPalindrome(s.toCharArray());
//當前訪問到的所有回文子串丹莲，所能觸及的最右一個字符的位置
int maxRight=0;
//maxRight對應對稱軸
int pos=0;
//記錄每個元素為對稱軸回文子串的長度
int[] RL = new int[chars.length];
//遍歷
for (int i=0;i<chars.length;i++){
int right;
if (i<maxRight){
//i關于pos的對稱位置：2*pos-i
//可以憑經(jīng)驗獲取的以i為對稱軸的最長回文子串：(maxRight-pos)*2+1
if(RL[2*pos-i]<(maxRight-pos)*2+1){
right = i+ RL[2*pos-i]/2+1;
}else{
right = maxRight+1;
}
}else{
right = i+1;
}
while(((2*i-right)>=0)&&right<chars.length&&chars[right]==chars[2*i-right]){
right++;
}
right--;
RL[i]=(right-i)*2+1;
if(right>maxRight){
maxRight = right;
pos = i;
}
}
return extractPalinadrome(RL,chars);
}
private String extractPalinadrome(int[] RL,char[] chars){
int maxLength=0;
int maxPos=0;
for (int i=0;i<chars.length;i++){
if(RL[i]>maxLength){
maxLength=RL[i];
maxPos=i;
}
}
char[] tempChars = new char[maxLength/2];
int index=0;
for(int i=maxPos-maxLength/2;i<=maxPos+maxLength/2;i++){
if(chars[i]!='#'){
tempChars[index]=chars[i];
index++;
}
}
return String.valueOf(tempChars);
}
private char[] pretreatmentPalindrome(char[] chars){
//字符數(shù)組預處理,轉(zhuǎn)換偶數(shù)長度的回文子串
//如 abdcccs 轉(zhuǎn)換成 #a#b#d#c#c#c#s#
char[] newChars = new char[chars.length*2+1];
for(int i=0;i<chars.length;i++){
newChars[2*i]='#';
newChars[2*i+1]=chars[i];
}
newChars[newChars.length-1]='#';
return newChars;
}
(4) 復雜度分析
空間復雜度：插入分隔符形成新串，占用了線性的空間大惺獭甥材；RL數(shù)組也占用線性大小的空間，因此空間復雜度是線性的性含。
時間復雜度：盡管代碼里面有兩層循環(huán)洲赵，通過amortized analysis我們可以得出，Manacher的時間復雜度是線性的商蕴。由于內(nèi)層的循環(huán)只對尚未匹配的部分進行叠萍，因此對于每一個字符而言，只會進行一次绪商，因此時間復雜度是O(n)苛谷。
