#KMP

#朴素模式匹配

就是暴力循环的解法

将文本串遍历的同时找到与模式串第一个字符相等的字符，开始尝试匹配

遍历模式串进行匹配，如果遍历完了都相等就是匹配成功，如果有不相等则匹配失败

失败后继续遍历文本串，下次匹配则从模式串的开头开始，这就是回溯到 0 下标

而文本串也没有随模式串遍历一起遍历，也是属于回溯了

KMP 算法就是解决这个模式串回溯长度的问题，并且还加快了遍历文本串，不用等待模式串遍历，一起遍历

function strStr(haystack: string, needle: string): number {
  for (let i = 0; i < haystack.length; i++) {
    if (haystack[i] === needle[0]) {
      let j = 0

      for (; j < needle.length && haystack[i + j] === needle[j]; j++) {}

      if (j === needle.length) {
        return i
      }
    }
  }

  return -1
}

#KMP

解决了两个回溯的问题：

模式串回溯问题：通过提前准备的 next 数组进行回溯而不是直接回溯到 0
文本串回溯问题：模式串与文本串一起遍历提高效率

难点就在 next 数组的准备上

#next 数组

next 数组就是最长相同前后缀表，也可以叫前缀和表

next 数组是用来回退的，它记录了模式串与文本串不匹配的时候，模式串应该从哪里开始重新匹配

next 数组的下标就是当前模式串字符下标

next 数组的值就是当前字符串(包括自己)的最长相同前后缀值

第一位永远是 0 因为一个字符没有前后缀

#最长相同前后缀

前缀就是最后字符外的前面的子串
后缀就是第一个字符外的后面的子串

最长相同前后缀就是前缀后缀相同的情况下，最长的前缀/后缀

如 aabaa

最长相同前后缀就是 aa

如 aabaaab

最长相同前后缀表就是[0,1,0,1,2,2,3]

#使用 next 数组匹配

如果匹配文本串 aabaabaafa，模式串 aabaaf

对应 next 是[0,1,0,1,2,0]

aabaab aafa aabaaf

因为 aabaaf 匹配到 f 时失败，f 之前的字符串为 aabaa，其最长相同前后缀为 aa

那么 next 表中 f 回退对应的位置就是 b

aabaabaafa ---aabaaf

那为什么回退到 b 就可以继续匹配了

你看，aab[aa]baafa括号中的 aa 在匹配时匹配的是aab[aa]f中括号的 aa

因为括号中的 aab[aa]f 为 f 前面字符串的后缀，其具有相同前缀[aa]baaf

那不就是也匹配过[aa]baaf中的 aa 了吗

那自然从 b 开始了

怎么在 next 数组中找到 b 的位置呢

f 匹配失败后应该从 next[fIndex-1]位置找

aabaa 字符串对应的值为 2

f 在 fIndex-1 位置找是因为 f 找的是 aabaa 的对应前缀和

2 再回到aabaaf中就是 b 了

#实现 next 数组

function getNext(needle: string) {
  let next = [0]
  // j为前缀尾部下标，next数组内的值本质就是j这个前缀下标
  let j = 0

  // i为后缀尾部下标，且遍历模式串
  for (let i = 1; i < needle.length; i++) {
    // 不同则前缀回退到相同的时候
    while (j > 0 && needle[j] !== needle[i]) {
      j = next[j - 1]
    }
    // 相同则前缀加一
    if (needle[j] === needle[i]) {
      j++
    }

    next[i] = j
  }

  return next
}

#解决模式串回溯问题

function strStr(haystack: string, needle: string): number {
  const next = getNext(needle)
  let j = 0 // 提到全局

  for (let i = 0; i < haystack.length; i++) {
    if (haystack[i] === needle[j]) {
      for (; j < needle.length && haystack[i + j] === needle[j]; j++) {}

      if (j === needle.length) {
        return i
      } else {
        // 只需要在每次匹配失败时使用next数组回退就行
        j = next[j - 1]
      }
    }
  }

  return -1
}

function getNext(needle: string) {
  let next = [0]
  // j为前缀尾部下标
  let j = 0

  // i为后缀尾部下标，且遍历模式串
  for (let i = 1; i < needle.length; i++) {
    // 不同则前缀回退到相同的时候
    while (j > 0 && needle[j] !== needle[i]) {
      j = next[j - 1]
    }
    // 相同则前缀加一
    if (needle[j] === needle[i]) {
      j++
    }

    next[i] = j
  }

  return next
}

#解决文本串回溯问题

function strStr(haystack: string, needle: string): number {
  const next = getNext(needle)
  let j = 0

  for (let i = 0; i < haystack.length; i++) {
    while (j > 0 && haystack[i] !== needle[j]) {
      j = next[j - 1]
    }

    if (haystack[i] === needle[j]) {
      j++
    }

    if (j === needle.length) {
      return i - (j - 1)
    }
  }

  return -1
}

function getNext(needle: string) {
  let next = [0]
  // j为前缀尾部下标
  let j = 0

  // i为后缀尾部下标，且遍历模式串
  for (let i = 1; i < needle.length; i++) {
    // 不同则前缀回退到相同的时候
    while (j > 0 && needle[j] !== needle[i]) {
      j = next[j - 1]
    }
    // 相同则前缀加一
    if (needle[j] === needle[i]) {
      j++
    }

    next[i] = j
  }

  return next
}