找出字符串中第一个匹配项的下标

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

普通方法

var strStr = function (haystack, needle) {
  let hLen = haystack.length;
  let nLen = needle.length;
  // 从第一个开始向后匹配
  for (let i = 0; i <= hLen - nLen; i++) {
    // 原始字符串的匹配位置
    let a = i;
    // 目标字符串的起始位置
    let b = 0;
    while (b < nLen && haystack[a] === needle[b]) {
      a++;
      b++
    }
    // 匹配成功返回起始位置
    if (b === nLen) return i
  }
  return -1
};

KMP 算法

在匹配出错时不把字符串完全回退重新下一位匹配，找到前缀表进行回退后继续匹配

前缀表 next数组

next数组就可以是前缀表，但是很多实现都是把前缀表统一减一（右移一位，初始位置为-1）之后作为next数组。

const next = new Array(needle.length).fill(0);
/**
    i：当前子串的后缀末尾
    j：上一项子串最长相等前后缀的下一项 或者 0 ，并且也是 上一项子串最长相等前后缀的长度

    i从1开始，j从0开始。因为 i 和 j都是0的话只有一个，肯定是0，相当于上面例子中的 a
*/
for (let i = 1, j = 0; i < m; i++) {
  1
  // while循环，要不断的向上寻找。
  while (j > 0 && needle[i] !== needle[j]) {
    // 如果不同，我们要从未匹配好的地方开始继续匹配。
    // 未匹配好的位置是那里呢？ 👇
    // 我们知道 next 数组的值就代表每一次子串匹配好的长度，
    // 因为数组是从0开始的，所以j - 1就指向了上一个子串未匹配好的位置。
    // 当j === 0时，说明要从头开始重新匹配了
    j = next[j - 1];
  }
  // 如果当前子串前后缀相等，就将更新子串，j++ i++
  if (needle[i] == needle[j]) {
    j++;
  }
  // 将当前子串的最长相等前后缀添加到next数组中
  next[i] = j;
}

var strStr = function (haystack, needle) {
  let n = haystack.length
  let m = needle.length
  if (m === 0) return 0

  let next = new Array(m).fill(0)
  for (let i = 1, j = 0; i < m; i++) {
    while (j > 0 && needle[i] !== needle[j]) {
      j = next[j - 1]
    }
    if (needle[i] === needle[j]) {
      j++
    }
    next[i] = j
  }
  
  for (let i = 0, j = 0; i < n; i++) {
    // 如果当前i 和 j不一致，就回退到上一个相等的位置的下一个看看是否匹配
    // 会不断回退，0为回退到边界，当回退到0意味着要重新从头开始匹配
    while (j > 0 && haystack[i] !== needle[j]) {
      j = next[j - 1]
    }
    if (haystack[i] === needle[j]) {
      j++
    }
    // 当j 和 m的长度相等时，就说明存在
    if (j === m) {
      return i - m + 1
    }
  }
  return -1
};