最长回文子串

共计 516 个字符，预计需要花费 2 分钟才能阅读完成。

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: “babad” 输出: “bab” 注意: “aba” 也是一个有效答案。
示例 2：
输入: “cbbd” 输出: “bb”
用的 Manacher 算法
var longestPalindrome = function(s) {
if (s.length == 0) return “”
var str=”$”
var j = 1,mx = 0,id = 0, len = [];
var max=0, index;
for(var i = 0, l = s.length; i < l; i++) {
str += “#”;
str += s[i]
}
str += “#”
for (var i = 1, l = str.length; i < l; i++) {
if(i < mx) {
len[i] = Math.min(len[2*id – i], mx – i)
} else {
len[i] = 1;
}
while(str[len[i] + i] == str[i – len[i]]) {
len[i]++;
}
if (len[i] + i > mx) {
id = i;
mx = len[i] + i;
if (len[i] > max) {
max = len[i];
index = i;
}
}
}
return s.substr((index – max) / 2, max – 1)
};