給定一個(gè)字符串 s，找到 s 中最長(zhǎng)的回文子串捻浦。
示例1：
輸入: "babad"
輸出: "bab"
注意: "aba" 也是一個(gè)有效答案隘膘。
示例2：
輸入: "cbbd"
輸出: "bb"
解決方法很多刀森，其中有一種時(shí)間復(fù)雜度達(dá)到了O(n)級(jí)別逝薪，就是Manachar算法隅要。在思想上很類似于KMP，同樣是利用已知信息減少重復(fù)操作董济。
一. 情況分析與預(yù)處理
- 可以發(fā)現(xiàn)的是步清，回文串有兩種情況
- 奇數(shù)回文：
aba回文中心是一個(gè)字符。 - 偶數(shù)回文：
bb回文中心是兩個(gè)字符中間虏肾。
- 奇數(shù)回文：
- 為了簡(jiǎn)化操作（兩種情況分別處理）廓啊，在每個(gè)字符左右添加特殊字符
#，將兩種情況合并為奇數(shù)封豪。
babad化為# b # a # b # a # d #
cbbd化為# c # b # b # d #
這時(shí)候回文中心必定是一個(gè)字符谴轮。
二. 如何獲取最長(zhǎng)回文子串長(zhǎng)度？
這里需要借助一個(gè)輔助數(shù)組p撑毛，用于記錄以每個(gè)字符為中心的最大回文半徑书聚。
- 輔助數(shù)組與預(yù)處理后的字符串?dāng)?shù)組等長(zhǎng)。
- 輔助數(shù)組對(duì)應(yīng)位置的值存放以該位置字符為中心的最長(zhǎng)回文子串長(zhǎng)度藻雌。（回文子串只有一個(gè)字符時(shí)為1）
index 0 1 2 3 4 5 6 7 8 9 10
arr # b # a # b # a # d #
p 1 2 1 4 1 4 1 2 1 2 1
得到兩個(gè)最大值（4）雌续，代表著以index=3和index=5兩個(gè)字符為中心的最大回文子串半徑都為4（這個(gè)長(zhǎng)度包含了特殊字符）。我們?nèi)コ厥庾址蟀l(fā)現(xiàn)這兩個(gè)子串為bab和aba胯杭，長(zhǎng)度為3驯杜。
- 在測(cè)試更多例子后我們可以發(fā)現(xiàn)這樣一個(gè)規(guī)律：最大的半徑
p[i]與最長(zhǎng)回文子串長(zhǎng)度maxLength存在這樣一種關(guān)系const maxLength = p[i] -1
二. 如何獲取最長(zhǎng)回文子串？
回歸題目做个，顯然獲取到最大長(zhǎng)度是不夠的鸽心，還需要知道開始的index。
let res = slice(最長(zhǎng)回文開始index居暖，index + maxLength)
那么顽频，如何獲取這個(gè)開始索引呢？Manachar算法給出了一個(gè)巧妙的方法太闺。
- 偶數(shù)回文情況
index 0 1 2 3 4 5 6 7 8
arr # c # b # b # d #
p 1 2 1 2 3 2 1 2 1
最大半徑index為4糯景，p[index] = 3，index - p[index] = 1省骂。在cbbd中index = 1剛好就是最長(zhǎng)回文bb的開始位置蟀淮。
- 奇數(shù)回文情況
index 0 1 2 3 4 5 6 7 8 9 10
arr # b # a # b # a # d #
p 1 2 1 4 1 4 1 2 1 2 1
最大半徑index為3，p[index] = 4钞澳，index - p[index] = -1怠惶。數(shù)組越界。
初步結(jié)論：最長(zhǎng)回文子串開始索引 = index - p[index]轧粟，但是奇數(shù)情況下不成立策治。
- 為了解決越界問題脓魏，我們?cè)赼rr前面和后面再添加一對(duì)特殊符號(hào)
$和@（必須成對(duì)加）
index 0 1 2 3 4 5 6 7 8 9 10 11 12
arr $ # b # a # b # a # d # @
p 1 2 1 4 1 4 1 2 1 2 1
再次使用剛才的結(jié)論，最大半徑index為4览妖，p[index] = 4轧拄，index - p[index] = 0揽祥，剛好是babad的最長(zhǎng)回文bab的開始索引讽膏。
- 奇數(shù)回文問題解決，加了兩個(gè)符號(hào)后偶數(shù)回文的情況：
index 0 1 2 3 4 5 6 7 8 9 10
arr $ # c # b # b # d # @
p 1 2 1 2 3 2 1 2 1
最大半徑index為5拄丰，p[index] = 3府树，index - p[index] = 2，結(jié)論需要修正料按，即(index - p[index]) / 2奄侠。（奇數(shù)情況下 / 2 不影響）
最終結(jié)論：最長(zhǎng)回文子串的開始索引 = (index - p[index]) / 2
三. 計(jì)算輔助數(shù)組p
- 計(jì)算p是整個(gè)算法最核心的地方，也不太好理解载矿。
- 設(shè)置兩個(gè)指針：
-
center：取得tail的回文子串的中心 -
tail：已知的最長(zhǎng)回文子串的最右端
-
- 整個(gè)過程是一次數(shù)組遍歷垄潮，假如我們現(xiàn)在要算p[i]（也就是前面的
0 <= j < i都已經(jīng)算完了）。-
情況1：i < tail
- i 仍然處于已知最長(zhǎng)子串的范圍內(nèi)闷盔，由于回文的對(duì)稱性弯洗，以
i為回文中心的子串在左邊能夠找到對(duì)應(yīng)的j子串。
其中：j = 2 * center - i - 但是需要注意的是逢勾，
i為中心的回文子串不一定整串都處于已知的center子串范圍內(nèi)牡整，也就是說有可能從右邊延展出去。在這種情況下溺拱，我們姑且認(rèn)為i的子串最多到tail位置了逃贝，大于tail的部分需要逐一匹配。這種時(shí)候迫摔，我們暫時(shí)認(rèn)為p[i] = tail - i
上面兩個(gè)結(jié)論綜合得到p[i] = Math.min(p[2*center - i],tail - i)
-
情況2：i > tail
當(dāng)i大于tail時(shí)沐扳，無法根據(jù)已知信息推斷i為中心的子串長(zhǎng)度，需要從中心開始擴(kuò)展句占。
-
四. JavaScript實(shí)現(xiàn)
function Manacher(str){
if(str.length < 2){
return str;
}
// 1.預(yù)處理沪摄，添加'#'以及前后兩個(gè)特殊字符'$'、'@'
let s = '$';
for(let i = 0;i < str.length;i++){
s += `#${str[i]}`;
}
s += '#@';
// 2.初始化輔助量
let center = 0;
let tail = 0;
let p = [];
let maxLength = -1;// 最長(zhǎng)回文子串的長(zhǎng)度
let index = 0;// 最長(zhǎng)回文子串的中心位置
// 2-1.遍歷s
for(let j = 1;j < s.length - 1;j++){
// 直接使用i < tail情況下的結(jié)論
p[j] = tail > j ? Math.min(p[2*center - j],tail - j) : 1;
// 中心向兩邊擴(kuò)展
while(s[j - p[j]] == s[j + p[j]]){
p[j]++;
}
// 如果新的回文串最右端大于tail辖众，就需要更新tail與center
if(tail < p[j] + j){
tail = p[j] + j;
center = j;
}
// 如果行的回文串大于maxLength卓起，那么就更新maxLength
if(maxLength < p[j] - 1){
maxLength = p[j] - 1;
index = j;
}
}
let begin = (index - maxLength) / 2;
return str.slice(begin,begin + maxLength);
}
