一天一大 lee(最短回文串)难度:困难-Day20200829

输入: "aacecaaa"
输出: "aaacecaaa"

输入: "abcd"
输出: "dcbabcd"

/**
 * @param {string} s
 * @return {string}
 */
var shortestPalindrome = function (s) {
  let len = s.length
  // 从长到短求最长前缀回文字符
  for (let i = len; i >= 0; i--) {
    let _result = s.substring(0, i)
    if (check(_result)) {
      return Array.from(s.substring(i, len)).reverse().join('') + s
    }
  }
  // 校验是否为回文字符串
  function check(x) {
    let str = '' + x
    return Array.from(str).reverse().join('') === str
  }
}

/**
 * @param {string} s
 * @return {string}
 */
var shortestPalindrome = function (s) {
  let len = s.length,
    str = s.split('').reverse().join('')

  // 正反字符匹配求最长匹配位数
  function kmp(query, pattern) {
    let fail = Array(len).fill(-1)
    // 最长公共前缀，不存在公共前缀填充-1
    for (let i = 1; i < len; ++i) {
      let j = fail[i - 1]
      while (j != -1 && pattern[j + 1] != pattern[i]) {
        j = fail[j]
      }
      if (pattern[j + 1] == pattern[i]) {
        fail[i] = j + 1
      }
    }
    // 校验  match记录匹配的位置
    let match = -1
    for (let i = 0; i < len; ++i) {
      // 如果当前不匹配匹配，指针跳跃到前缀位置开始匹配
      while (match != -1 && pattern[match + 1] != query[i]) {
        match = fail[match]
      }
      // 如果当前位匹配，逐个向后匹配
      if (pattern[match + 1] == query[i]) {
        ++match
      }
    }
    return match
  }

  let num = kmp(str, s),
    add = num == len - 1 ? '' : s.substring(num + 1)
  return Array.from(add).reverse().join('') + s
}