前言：力扣刷题
问题：
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。
示例：
输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。
思路：
看到这个题我就想到了我之前学过的KMP算法，这道题肯定要使用到KMP算法思想。
haystack为主串，needle是子串。
用于在字符串haystack中查找子串needle的第一次出现位置。算法使用了KMP算法中的next数组，用于记录子串中每个字符的最长相同前后缀长度。
具体来说，算法首先生成子串needle的next数组，然后使用两个指针i和j分别指向字符串haystack和子串needle的第一个字符，然后开始遍历字符串。
如果当前字符匹配，则两个指针都后移一位；
如果不匹配，则将指向子串的指针j更新为已匹配的最长相同前后缀长度，然后继续比较；
如果子串的指针j已经到达末尾，则说明已经找到了匹配的子串，返回起始位置即可。
基于上述思考，代码如下：
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
def get_next():
for i in range(1, n):
k = next_[i - 1]
while needle[i] != needle[k]:
if k == 0:
k -= 1
break
else:
k = next_[k - 1]
next_[i] = k + 1
n = len(needle)
next_ = [0] * n
get_next()
i = 0
j = 0
while i < len(haystack):
if haystack[i] == needle[j]:
i += 1
j += 1
elif j == 0:
i += 1
else:
j = next_[j - 1]
if j >= n:
return i - n
return -1
设索引i指向主串当前进行匹配的字符，索引j指向子串当前进行匹配的字符：
如果当前字符相同，那么两个索引都后一位，继续匹配
如果当前字符不同，且索引j = 0，说明第一个字符就不匹配，索引i后移一位。
如果当前字符不同，且索引j > 0，说明在索引i和j发生了失配，j移动到next[j]的位置继续匹配。
执行结果如下图：
学习到的知识点：
温习KMP算法，哈哈哈还是考研的时候学习的KMP匹配算法，又想了好久才想起来🤣。
