leetcode #5 Longest Palindromic

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"

• 题目大意
  最大回文子串。给定一个字符串，找到他最长的回文子串。

这道题有很多种解法。

• 最基本的思想是遍历每个字符作为回文串的中心点 然后向左右扩展 直到两边不相同或者到达边界。注意区分奇数长度和偶数长度的情况。时间复杂度O(n ² )
• 其次想到了动态规划用a[i,j] 表示 第i个字符到第j个字符是否为回文串。 状态转移方程为：a[i,j] = (s.charAt(j)==s.charAt(i)) && (j-i<2 || a[i+1,j-1])。
  时间复杂度同样是O(n²)
• 接下来就要隆重介绍一种专门求最长回文子串的算法了: Manacher 算法

首先在方法一中 我们要对奇数和偶数的情况区分对待。该算法巧妙的在每个字符之间加入了一个特殊字符（原串中没有出现过的即可）。这样我们只需要考虑奇数的情况了。举例说明： 假设原字符串为 babad， 我们再每个字符之间加入空格将其变成：‘!b!a!b!a!d!'. 不难发现，在新的字符串中的回文子串在旧的字符串中也是回文的。

Manacher 算法的核心是维护了一个一维数组 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

不难发现，最长的回文子串是max(Radius[i])-1.
为了高效的求出radius数组，该算法引入了两个变量maxIndex和maxRight. maxIndex 记录了到目前为止最长的回文子串的中心的索引坐标；maxRight记录了该最长回文子串最右的字符的坐标。

该算法是如何通过这两个变量得到当前i 的radius[i]呢？分为两种情况讨论：

• i < maxRight
  情况大概如下：
  ...j-radius[j]....j....j+radius[j]..maxIndex...i-radius[j]....i....i+radius[j]........maxRight........
  j 是i关于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.

再此基础上我们将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;
}