给你两个字符串 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 。
看到这道题我的第一反应是直接indexOf秒了
/*** @param {string} haystack* @param {string} needle* @return {number}*/
var strStr = function(haystack, needle) {return haystack.indexOf(needle)
};在业务中当然是直接用轮子，但是算法题的目的是让我们造轮子，这道题考察的是KMP算法。
KMP算法是什么？
KMP算法（Knuth-Morris-Pratt算法）是一种高效字符串匹配算法，主要用于在主串（文本）中快速定位子串（模式）的起始位置。
我们要做的实际上主要是去为子串建立next数组，那么什么是next数组？next数组是用来记录对应位置的相同前后缀字符的长度
名词解释：
| 名词 | 解释 |
|---|---|
| 前缀 | 不包含末尾的所有字符串 |
| 后缀 | 不包含开头的所有字符串 |
如何实现next数组？先上代码：
let next = [0]let i = 1let prefix_len = 0while (i < needle.length) {if (needle[i] == needle[prefix_len]) {prefix_len += 1next.push(prefix_len)i += 1} else {if (prefix_len == 0) {next.push(prefix_len)i += 1} else {prefix_len = next[prefix_len - 1]}}}图解如下
next[i]=0 prefix_len=0
next[i]=0 prefix_len=0
next[i]=1 prefix_len=1
next[i]=0 prefix_len=0
next[i]=1 prefix_len=1
next[i]=2 prefix_len=2
next[i]=3 prefix_len= 3
next[i]=2 prefix_len=2
这里注意： prefix_len指的是相同前后缀的长度。
理解了next数组，那下面的这段也就可以理解了，主串和子串按位比较，如果有不同， 子串就后移（主串指针后移）
/*** @param {string} haystack* @param {string} needle* @return {number}*/
var strStr = function (haystack, needle) {let next = [0]let i = 1let prefix_len = 0while (i < needle.length) {if (needle[i] == needle[prefix_len]) {prefix_len += 1next.push(prefix_len)i += 1} else {if (prefix_len == 0) {next.push(prefix_len)i += 1} else {prefix_len = next[prefix_len - 1]}}}let n = haystack.lengthlet m = needle.lengthfor (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
};