找出字符串中第一个匹配项的下标
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。
示例 1：
codeType
输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。
示例 2：
codeType
输入：haystack = "leetcode", needle = "leeto"
输出：-1
解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。
提示：
codeType
1 <= haystack.length, needle.length <= 104
haystack 和 needle 仅由小写英文字符组成
解法：
解法一：暴力法
逐个检测是否匹配，如果不匹配就回退。时间复杂度O(mn)
typescript
function strStr(haystack: string, needle: string): number {
// 暴力法
// 逐个检测是否匹配，如果不匹配就回退，时间复杂度应该是O(mn)
const n = haystack.length
const m = needle.length
let i = 0
while(i<n){
let j = 0
while(j<m && i<n){
if(haystack[i] === needle[j]){
i++
j++
if(j===m){
return i - m
}
}else{
i = i - j // 回退
break
}
}
i++
}
return -1
};
解法二：KMP算法
kmp的核心思想就是子串每个位置匹配到后回退的位置是一定的。这只和子串有关，所以可以先用子串求出next数组。求next数组的时间复杂度是O(m)，匹配过程时间复杂度是O(n)。最终的时间复杂度是O(m+n)
next数组的本质就是到位置j时，子串的最长公共前缀、后缀。next数组的数值表示在该位置匹配失败时，可以跳过几个字符。
next数组的求解可以暴力获得，但是也可以利用递推的方式求解
具体过程可以看该教程：kmp算法视频
其中比较难以理解的地方在于匹配失败时的回退，在这里C和B匹配失败，需要寻找更短的公共前后缀。
只需要
j=next[j-1]，也就是3，对应的值next[j]=1，所以最长公共前后缀就变成了1，从该位置继续匹配。
typescript
function strStr(haystack: string, needle: string): number {
// 数据结构中经典的KMP算法
// 求出next数组，之后遍历就不需要完全回退了。
const n = haystack.length
const m = needle.length
// kmp的核心思想就是子串每个位置匹配到后回退的位置是一定的。
// 这只和子串有关，所以可以先用子串求出next数组
const next = [0]
let i=1,j=0
while(i<m){
// 匹配不成功，j回退
while (j > 0 && needle[i] !== needle[j]) {
j = next[j - 1]
}
// 匹配成功，一起后移
if (needle[i] == needle[j]) {
j++
}
next[i] = j
i++
}
i = 0
j = 0
while(i<n){
while(j>0 && haystack[i] !== needle[j]){
// 匹配不成功，j回退
j = next[j-1]
}
// 匹配成功，两个指针都后移
if(haystack[i] === needle[j]){
j++
}
if(j === m){ // 完全匹配
return i - m + 1
}
i++
}
return -1
};