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 2 )
- 其次想到了动态规划用a[i,j] 表示 第i个字符到第j个字符是否为回文串。 状态转移方程为：a[i,j] = (s.charAt(j)==s.charAt(i)) && (j-i<2 || a[i+1,j-1])。
时间复杂度同样是O(n2) - 接下来就要隆重介绍一种专门求最长回文子串的算法了: 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;
}
