字符串算法：回文 / 子串 / KMP 思想

// 运行环境：Node.js 14+
// 保存为 dsa-l9.js，执行：node dsa-l9.js

function longestPalindrome(s) {
  let start = 0, maxLen = 1
  function expand(l, r) {           // 从中心 l,r 向两侧扩
    while (l >= 0 && r < s.length && s[l] === s[r]) { l--; r++ }
    const len = r - l - 1
    if (len > maxLen) { maxLen = len; start = l + 1 }
  }
  for (let i = 0; i < s.length; i++) {
    expand(i, i)     // 奇数长中心
    expand(i, i + 1) // 偶数长中心
  }
  return s.slice(start, start + maxLen)
}
console.log(longestPalindrome('babad')) // 'bab' 或 'aba'

// 手写 strStr：在 haystack 中找 needle 首次出现下标（KMP 版 O(n+m)）
function strStr(haystack, needle) {
  if (needle === '') return 0
  const n = needle.length
  const lps = new Array(n).fill(0) // longest prefix-suffix
  for (let i = 1, len = 0; i < n; i++) {
    while (len && needle[i] !== needle[len]) len = lps[len - 1]
    if (needle[i] === needle[len]) lps[i] = ++len
  }
  for (let i = 0, j = 0; i < haystack.length; i++) {
    while (j && haystack[i] !== needle[j]) j = lps[j - 1]
    if (haystack[i] === needle[j]) j++
    if (j === n) return i - n + 1
  }
  return -1
}
console.log(strStr('hello', 'll')) // 2