参考链接

KMP算法

动画演示

KMP动画演示

参考代码

function genNext(pattern) {
  let len = pattern.length
  let next = [-1]

  let i = 0
  let j = -1

  while (i < len - 1) {
    if (j == -1 || pattern[i] == pattern[j]) {
      i++
      j++
      next[i] = j
    } else {
      j = next[j]
    }
  }
  return next
}

function kmp(target, pattern) {
  let pLen = pattern.length
  let tLen = target.length

  let i = 0
  let j = 0
  let next = genNext(pattern)
  while (j < pLen && i < tLen) {
    if (j === -1 || pattern[j] == target[i]) {
      i++
      j++
    } else {
      j = next[j]
    }
  }

  if (j === pLen) {
    return i - j
  } else {
    return -1
  }
}

console.log(kmp("aaaacdbf", "cdbf"))