KMP算法

next 函数

function get_next(str) {
  const next = Array(str.length).fill(0)
  let i = 1
  let m = 0

  while (i < str.length) {
    if (str[i] === str[m]) {
      next[i] = ++m
      i++
    }
    if (str[i] !== str[m]) {
      if (m === 0) {
        next[i] = 0
        i++
      } else {
        m = next[m - 1]
      }
    }
  }
  return next
}

kmp 函数

function kmp(str, subStr) {
  let i = 0
  let j = 0

  const next = get_next(subStr)

  while (i <= str.length) {
    if (subStr[j] === str[i]) {
      i++
      j++
      if (j === subStr.length) {
        return i - j
      }
    } else {
      if (j === 0) {
        i++
      } else {
        j = next[j - 1]
      }
    }
  }
  return -1
}

next[j]就是模式串"p1…pj"中最大公共前后缀长度，如果没有就+1（即 next[j-1]+1）；kmp 匹配中失配时，i 不变（主串不回溯），j = next[j]，然后继续往后匹配。如果 j == 0，i 和 j 都+1。如果 j 大于模式串长度即匹配成功，返回 i - 模式串长度作为结果。

比如模式串"abaabcac"，next[] = [0,1,1,2,2,3,1,2]

a 0 （next[1] == 0）

ab 1 （没有公共前后缀，+1。next[2] = next[1]+1，即 next[2]==1）

aba 1 （最长公共前后缀"a"，长度 1）

abaa 2 （没有公共前后缀，+1）

abaab 2（最长公共前后缀"ab"，长度 2）

abaabc 3 （没有公共前后缀，+1）

abaabca 1（最长公共前后缀"a"，长度 1）

abaabcac 2 （没有公共前后缀，+1）