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

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

示例 1：

输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。

示例 2：

输入：haystack = "leetcode", needle = "leeto"
输出：-1
解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。

当面对这个问题你的第一反应是什么，首先我的第一反应是：

var strStr = function(haystack, needle) {
    return haystack.indexOf(needle)
};

实际上他想考察什么呢？

难道考察对API的应用吗，我想不是的，这就引出了今天要讲的主角——KMP算法

KMP的绝招就是next数组——一个“失败跳转指南”，告诉你在匹配失败时应该回退到哪里，而不是回到开头

正常暴力解法，可能双重循环，文本内容回到索引+1，被匹配内容索引回到0

关键思想：失败时，不是两个指针都后退，而是只退模式串指针，文本串指针继续前进！

📦 先看Next数组构建

function buildNext(pattern) {
  const next = [0];  // 第一个字符没有前后缀，肯定是0
  let i = 1;         // 当前考察的位置
  let prefixLen = 0; // 当前匹配的前缀长度
  
  while (i < pattern.length) {
    if (pattern[i] === pattern[prefixLen]) {
      // 字符匹配上了！前缀长度+1
      prefixLen++;
      next[i] = prefixLen;
      i++;
    } else {
      if (prefixLen === 0) {
        // 没匹配上，而且前缀长度为0
        next[i] = 0;
        i++;
      } else {
        // 关键！没匹配上，但前缀长度不为0
        // 利用已经算好的next值进行回退
        prefixLen = next[prefixLen - 1];
      }
    }
  }
  
  return next;
}

// 举个🌰：pattern = "ababa"
// 手动算一下：
// a       -> 0
// ab      -> 0
// aba     -> 1 (前缀"a" = 后缀"a")
// abab    -> 2 (前缀"ab" = 后缀"ab")
// ababa   -> 3 (前缀"aba" = 后缀"aba")
// 所以 next = [0, 0, 1, 2, 3]

🎯 核心要点

1. 为什么是模式串建next？

因为模式串是已知的、固定的，可以提前分析它的"自我相似性"。

2. 前缀后缀公共长度代表什么？

代表：在当前位置失败时，前面已经匹配的部分中，有多少可以直接复用。

直观对比：暴力 🆚 KMP

文本串：  a b c a b x a b c a b c
模式串：  a b c a b c
         ↑ ↑ ↑ ↑ ↑ ❌ 第5个字符不匹配

暴力算法：文本指针回退到b，模式指针回退到a
         a b c a b x a b c a b c
           a b c a b c
          ← 完全重来！

KMP算法：文本指针停在x，模式指针跳到c
         a b c a b x a b c a b c
               a b c a b c
              ← 只退模式指针！
              
为什么能跳到c？因为前面匹配的"ab" = 模式串开头的"ab"

具体实现：

var strStr = function(haystack, needle) {
    let left = 0;
    let right = 0;
    let next = buildNext(needle);
    while (left < haystack.length) {
        if (haystack[left] == needle[right]) {
            left++;
            right++;
        } else {
            if (right > 0) {
               right = next[right - 1] 
            } else {
                left++
            }
        }
        if (right == needle.length) {
            return left - right;
        }
    }
    return -1;
};
var buildNext = function(params) {
    let next = [0];
    let len = 0;
    let i = 1;
    while(i < params.length) {
        if (params[i] === params[len]) {
            len++;
            next[i] = len;
            i++
        } else {
            if (len === 0) {
                next[i] = 0;
                i++;
            } else {
                len = next[len - 1]
            }
        }
    }
    return next
}