Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example:
Input: "cbbd"
Output: "bb"

• 題目大意
  最大回文子串。給定一個字符串，找到他最長的回文子串。

這道題有很多種解法。

• 最基本的思想是遍歷每個字符作為回文串的中心點 然后向左右擴展 直到兩邊不相同或者到達邊界。注意區(qū)分奇數(shù)長度和偶數(shù)長度的情況。時間復(fù)雜度O(n ² )
• 其次想到了動態(tài)規(guī)劃用a[i,j] 表示 第i個字符到第j個字符是否為回文串。 狀態(tài)轉(zhuǎn)移方程為：a[i,j] = (s.charAt(j)==s.charAt(i)) && (j-i<2 || a[i+1,j-1])。
  時間復(fù)雜度同樣是O(n²)
• 接下來就要隆重介紹一種專門求最長回文子串的算法了: Manacher 算法

首先在方法一中 我們要對奇數(shù)和偶數(shù)的情況區(qū)分對待。該算法巧妙的在每個字符之間加入了一個特殊字符（原串中沒有出現(xiàn)過的即可）。這樣我們只需要考慮奇數(shù)的情況了。舉例說明： 假設(shè)原字符串為 babad， 我們再每個字符之間加入空格將其變成：‘!b!a!b!a!d!'. 不難發(fā)現(xiàn)，在新的字符串中的回文子串在舊的字符串中也是回文的。

Manacher 算法的核心是維護了一個一維數(shù)組 Radius[i],代表以第i個字符為中心的回文子串的半徑。 舉例說明：

字符串: ! b ! a ! b ! a ! d !
index : 0 1 2 3 4 5 6 7 8 9 10
Radius: 1 2 1 4 1 4 1 2 1 2 1

不難發(fā)現(xiàn)，最長的回文子串是max(Radius[i])-1.
為了高效的求出radius數(shù)組，該算法引入了兩個變量maxIndex和maxRight. maxIndex 記錄了到目前為止最長的回文子串的中心的索引坐標(biāo)；maxRight記錄了該最長回文子串最右的字符的坐標(biāo)。

該算法是如何通過這兩個變量得到當(dāng)前i 的radius[i]呢？分為兩種情況討論：

• i < maxRight
  情況大概如下：
  ...j-radius[j]....j....j+radius[j]..maxIndex...i-radius[j]....i....i+radius[j]........maxRight........
  j 是i關(guān)于maxIndex 的對稱點，因此 [i-radius[j],i+radius[j]] 一定是回文的 （因為[j-radius[j],j+radius[j]]是回文的。
  注意，如果i+radius[j]>maxRight,
  此時只能保證[i-(maxRight-i),maxRight] 是回文的。
  所以 radius[i] 的初始值為
  min( maxRight-i, radius[maxIndex-(i-maxIndex)] ）

• i >= maxRight;
  此時我們沒有任何線索 radius[i] = 1.

再此基礎(chǔ)上我們將radius[i] 向左右延展找到最大的以i為中心的子串，并且更新maxRight和maxIndex.

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    let maxRight=0;
    let maxIndex=0;
    let radius=[];
    let maxLen=0;
    let ansIndex=0;
    let newString='!'+s.split('').join('!')+'!';
    for (let i=0;i<newString.length;i++){
        if (i<maxRight){
            radius[i]=min(maxRight-i,radius[maxIndex-(i-maxIndex)]);
        }
        else{
            radius[i]=1;
        }
        while (i-radius[i]>=0 && i+radius[i]<newString.length && newString[i-radius[i]]==newString[i+radius[i]]){ //向左右擴展
            radius[i]++;
        }
            
        if (radius[i]+i-1>maxRight){ 更新maxRight
            maxRight=radius[i]+i-1;
            maxIndex=i;
        }
        if (radius[i]>maxLen){ 記錄最大值
            maxLen=radius[i];
            ansIndex=i;
           
        }
    }
    return  newString.substring(ansIndex-radius[ansIndex]+1,ansIndex+radius[ansIndex]).split('!').join('');;
};

function min(a,b){
    return a<b?a:b;
}