/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    let m = []
    let res = ''
    for(let i=0; i<s.length; i++) {
        for(let j = i; j < s.length; j++) {
            m.push(s.slice(i, j+1))
        }
    }
    m.sort(function(a,b){
        return b.length - a.length
    })
    for (let i of m) {
        if (i === i.split('').reverse().join('')) {
            res = i
            break;
        }
    }
    return res
}

var longestPalindrome = function(s) {
    let m = []
    let res = ''
    for(let i=0; i<s.length; i++) {
        for(let j = i; j < s.length; j++) {
            if (s[i] != s[j]) break
            let ele = s.slice(i, j+1)
            if (ele === ele.split('').reverse().join('') && ele.length > res.length) {
                res = ele
            }
        }
    }
    return res
}

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    let rs = s.split('').reverse().join('')
    let size = s.length
    let len = 0
    let end = 0
    let a = new Array(size)
    for (let i = 0; i < size; i++) {
        a[i] = new Array()
    }
    for (let i = 0; i < size; i++) {
        for(let j = 0; j < size; j++) {
            if (s[i] === rs[j]) {
                if (i > 0 && j > 0) {
                    a[i][j] = a[i-1][j-1] + 1
                } else {
                    a[i][j] = 1
                }

                if(a[i][j] > len) {
                    let beforeIndex = size - 1 - j
                    if (beforeIndex + a[i][j] -1 == i) { 
                        len = a[i][j]
                        end = i
                    }
                }
            } else {
                a[i][j] = 0
            }
        }
    }
    return s.slice(end-len+1, end+1)
}

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    let size = s.length
    let start = 0
    let len = 0 //字串長(zhǎng)度
    // 奇數(shù)長(zhǎng)度的回文字串
    for (let i = 0; i < size; i++) {
        let left = i - 1
        let right = i + 1
        while (left >= 0 && right < size && s[left] == s[right]) {
            left --
            right ++
        }
        if (right - left - 1 > len) {
            start = left +1
            len = right -left -1
        }
    }
    // 偶數(shù)長(zhǎng)度的回文字串
    for (let i = 0; i < size; i++) {
        let left = i
        let right = i + 1
        while (left >= 0 && right < size && s[left] == s[right]) {
            left--
            right++
        }
        if (right -left -1 > len) {
            start = left + 1
            len = right -left -1
        }
    }
    return s.slice(start, start + len)
}

// 第一步
var longestPalindrome = function(s) {
    let size = s.length
    if (size < 2) {
        return s
    }
    let str = addBoundaries(s, '#')
    let formatSize = 2 * size +1
    let maxSize = 1

    let start = 0
    for (let i=0; i<formatSize; i++) {
        let curSize = centerSpread(str, i)
        if (curSize > maxSize) {
            maxSize = curSize
            start = (i - maxSize)/2
        }
    }
    return s.slice(start, start + maxSize)
}

// 處理原字符串
var addBoundaries = function(s, divide) {
    let size = s.length
    if (size === 0) {
        return ''
    }
    if (s.indexOf(divide) != -1) {
        throw new Error('參數(shù)錯(cuò)誤，您傳遞的分割字符，在輸入字符串中存在！')
    }
    return divide + s.split('').join(divide) + divide
}

// 輔助數(shù)組
var centerSpread = function(s, center) {
     // left = right 的時(shí)候，此時(shí)回文中心是一個(gè)空隙，回文串的長(zhǎng)度是奇數(shù)
    // right = left + 1 的時(shí)候，此時(shí)回文中心是任意一個(gè)字符，回文串的長(zhǎng)度是偶數(shù)
    let len = s.length
    let i = center - 1
    let j = center + 1
    let step = 0
    while (i >= 0 && j < len && s.charAt(i) == s.charAt(j)) {
        i--
        j++
        step++
    }
    return step
}
longestPalindrome('ababadfglldf;hk;lhk')

// 完整
var longestPalindrome = function(s) {
    let size = s.length
    if (size < 2) {
        return s
    }
    let str = addBoundaries(s, '#')
    let formatSize = 2 * size +1

    let p = new Array(formatSize).fill(0)

    let maxRight = 0
    let center = 0

    let maxSize = 1

    let start = 0
    for (let i=0; i<formatSize; i++) {
        if (i < maxRight) {
            let mirror = 2 * center - i;
            // Manacher 算法的核心
            p[i] = Math.min(maxRight - i, p[mirror]);
        }
        // 下一次嘗試擴(kuò)散的左右起點(diǎn)，能擴(kuò)散的步數(shù)直接加到 p[i] 中
        let left = i - (1 + p[i]);
        let right = i + (1 + p[i]);

        // left >= 0 && right < formatSize 保證不越界
        // str.charAt(left) == str.charAt(right) 表示可以擴(kuò)散 1 次
        while (left >= 0 && right < formatSize && str.charAt(left) == str.charAt(right)) {
            p[i]++;
            left--;
            right++;

        }
        // 根據(jù) maxRight 的定義，它是遍歷過的 i 的 i + p[i] 的最大者
        // 如果 maxRight 的值越大，進(jìn)入上面 i < maxRight 的判斷的可能性就越大，這樣就可以重復(fù)利用之前判斷過的回文信息了
        if (i + p[i] > maxRight) {
            // maxRight 和 center 需要同時(shí)更新
            maxRight = i + p[i];
            center = i;
        }
        if (p[i] > maxSize) {
            // 記錄最長(zhǎng)回文子串的長(zhǎng)度和相應(yīng)它在原始字符串中的起點(diǎn)
            maxSize = p[i];
            start = (i - maxSize) / 2;
        }
    }
    return s.slice(start, start + maxSize)
}

var addBoundaries = function(s, divide) {
    let size = s.length
    if (size === 0) {
        return ''
    }
    if (s.indexOf(divide) != -1) {
        throw new Error('參數(shù)錯(cuò)誤，您傳遞的分割字符，在輸入字符串中存在！')
    }
    return divide + s.split('').join(divide) + divide
}
longestPalindrome('babb')