最近刷leetcode時(shí)，遇到求最長回文子串問題彪见，一開始想的是暴力匹配算法（逐個(gè)字符向兩邊檢索）儡司，發(fā)現(xiàn)花費(fèi)時(shí)間過長，后來了解到Manacher算法企巢，跟大家分享一下枫慷。
一、字符串處理
在暴力匹配算法中浪规，我們以某個(gè)字符為對稱中心或听，分別向兩邊檢索，但問題出現(xiàn)了笋婿。
如果回文子串長度為奇數(shù)誉裆，如： ababa
當(dāng)我們逐個(gè)匹配時(shí)，肯定會找到最長子串缸濒，
但如果長度為偶數(shù)時(shí)足丢， 如: abaaba
這時(shí)對稱中心不是某個(gè)字符，匹配失敗庇配。
所以斩跌，為了解決這種問題，我們需要對字符串進(jìn)行處理
處理前： ababa
處理后: #a#b#a#b#a#
其中'#'為特殊處理字符捞慌，你也可以選擇其它不在字符串中的字符
二耀鸦、計(jì)算長度
我們用一個(gè)數(shù)組 len 來表示處理后回文字符串的長度，len[i] 表示以第i個(gè)字符為對稱中心的回文字符串的半徑+1（自身）啸澡，len[i] -1 表示原字符串(處理前)中以第i個(gè)字符為對稱中心的回文子串長度袖订。如:
字符串: # a # b # a # b # a #
len[]: 1 2 1 4 1 6 1 4 1 2 1
len-1: 0 1 0 3 0 5 0 3 0 1 0
i : 0 1 2 3 4 5 6 7 8 9 10
我們可以循環(huán)遍歷求得len數(shù)組，但這樣和暴力匹配算法沒啥區(qū)別嗅虏，所以我們來看看Manacher的精髓:
假設(shè)我們求 len[i] 的值洛姑，我們設(shè) len[j] ( j < i ) 中的最大值為R,對應(yīng)的下標(biāo)為J,其意義是以第J個(gè)字符為對稱中心的回文子串 (記為S) 的 半徑+1 = R。Tl,Tr分別為S的左右端點(diǎn)皮服。如圖：
這時(shí)楞艾，我們需要對 i 所處的位置情況進(jìn)行討論：
當(dāng) i >= Tr参咙，即：
我們需要依次往兩邊匹配，直到達(dá)到邊界产徊，或者字符不相等昂勒。
當(dāng) i < Tr，關(guān)于 點(diǎn)J 作 i 對稱點(diǎn) ii舟铜，以下標(biāo)ii 為對稱中心的回文字符串記為s：
當(dāng) s 的右端點(diǎn) <= J,即 ii + len[ii] -1 <= J：
此時(shí) len[i] = len[ii]
當(dāng) s 的 右端點(diǎn) > J 我們會得到一個(gè)必定回文區(qū)域戈盈，
然后在該區(qū)域的端點(diǎn)往兩邊匹配，直到到達(dá)邊界谆刨，或者字符不相等塘娶。
經(jīng)過一番比較匹配后，我們會得到 len[ i ] ,如果 len [ i ] > R ( ps: len [ J ] ),
則另 R = len [ i ] , J = i ,再計(jì)算 len [ i +1 ] ,直到達(dá)到邊界痊夭。
代碼實(shí)現(xiàn)
......
int R = 0,J = 0;
for (int i = 0; i <s.length() ; i++) {
if(i < R){
len[i] = Math.min(len[2 * J - i],R-i); // 尋找最短公共半徑
}else{
len[i] = 1; // len[i] = 半徑 + 自身刁岸， 所以初始化為1
}
while(i - len[i] >= 0 && i + len[i] <s.length()
&& s.charAt(i- len[i]) == s.charAt(i + len[i])){
len[i] += 1;
}
if(len[i] > R){
R = len[i];
J = i;
}
}
......
參考文章：
最長回文子串——Manacher 算法
