leecode 0005.最长回文子串

题目描述

给你一个字符串 s，找到 s 中最长的回文子串。

示例

输入：s = “babad”
输出：”bab”
解释：”aba” 同样是符合题意的答案。

输入：s = “cbbd”
输出：”bb”

思路

Manacher-方法介绍

关键词：回文半径

关键变量：向右延伸最远回文串中心c、向右延伸最远回文串右边界r

记录变量：最长回文串中心pos、最长回文串半径len

Code

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    let t = "#";
    for(let i = 0; i < s.length; ++i) {
        t += s[i] + '#';
    }
    const arr = new Array(t.length).fill(1);//radius + 1
    let c = 0, r = 0, len = 0, pos = 0;
    for(let i = 1; i < t.length; ++i) {

        //reduce while times below
        (r > i) && (arr[i] = Math.min(arr[2 * c - i], r - i));

        while(i + arr[i] < t.length &&
              i - arr[i] >= 0 &&
              t[ i + arr[i] ] === t[ i - arr[i] ]) {
            ++arr[i];
        }

        if(r < i + arr[i]) {
            r = i + arr[i];
            c = i;
        }
        if(len < arr[i]) {
            len = arr[i];
            pos = i;
        }
    }
    const center = parseInt(pos / 2);
    const start = center - (len / 2 - 1);
    return s.substring(start, start + (arr[pos] - 1));
};

console.log(longestPalindrome("a"));