题目表述：
给你两个字符串 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 。
提示：
1 <= haystack.length, needle.length <= 104haystack和needle仅由小写英文字符组成
力扣链接：
思路分析：
这道题是一道典型的字符串匹配的题目，我们应该迅速想到KMP算法。关于KMP算法的知识点，我们主要分为两个部分，第一是求解前缀表；第二是使用前缀表来匹配字符串。
1.获取前缀表：关于前缀表，我们需要新定义三个变量，定义两个指针i和j，j指向前缀末尾位置，i指向后缀末尾位置。一个next列表（前缀表），next[i] 表示 i（包括i）之前最长相等的前后缀长度（其实就是j）。初始化j为0，next[0]=0
遍历i，由1到len(s)。当s[i]与s[j]不相等并且j>0时，j往前回退，回退到前一个字符的next值代表的下标位置去，这个while可以持续判断并进行回退操作；当s[i] ==s[j]时， j加1；将j的当前值赋给当前下标为i的字符的next值。
2.利用前缀表进行字符串匹配：
首先对模式串的长度进行判断，如果模式串的长度为0，则返回0；
预定义前缀表为固定长度的列表，并调用getNext方法获取前缀表；
遍历i，从0到 len(haystack), 当j>0并且文本串与模式串在i下标的位置不匹配时，j返回前一个模式串j位置的前一个字符的next值所代表的下标位置，此判断和过程持续进行直到不满足循环条件；如果haystack[i] == needle[j]，即文本串下标i的字符与模式串下标j的字符相等时，j加1，即模式串中j的位置向后移一位；当j的值等于模式串的长度时，返回i-len(needle)+1, 即返回匹配成功的起始点。
代码分析：
# 前缀表从0开始，不减1
class Solution:
def getNext(self, next: List[int], s: str) -> None:
# 初始化j指针和next数组(前缀表)
j=0
next[0] = 0
for i in range(1, len(s)): # i从1开始
# 当前后缀不相等的情况,此处用while进行持续判断，直到这两个条件不同时满足
# 必须保证j>0
while j>0 and s[i] != s[j]:
j = next[j-1] # j向前回退一个，看前一个字符的next值
# 如果前后缀相等，则更新前缀指针j
if s[i] == s[j]:
j += 1
next[i] = j # 将前缀的长度j赋值给next[i]
def strStr(self, haystack:str, needle:str) -> int:
# 文本串是haystack; 模式串是needle
if len(needle) == 0:
return 0
# 预定义前缀表
next = [0] * len(needle)
# 调用getNext方法获取next数组
self.getNext(next, needle)
j = 0
# i从0开始，遍历文本串
for i in range(len(haystack)):
#
while j>0 and haystack[i] != needle[j]:
j = next[j-1] # j返回前一个next表的位置
if haystack[i] == needle[j]:
j += 1 # 如果匹配则j+1
if j == len(needle): # 当前缀的长度模式串的长度相等时，返回匹配的起始位置。
return i- len(needle) + 1
return -1 # 返回-1，表示不匹配。这里还有其它的几种简单的偷懒方法也给大家提供，不建议使用。
# 使用两个for循环暴力求解
class Solution(object):
def strStr(self, haystack, needle):
"""
:type haystack: str
:type needle: str
:rtype: int
"""
m, n = len(haystack), len(needle)
for i in range(m):
if haystack[i:i+n] == needle:
return i
return -1 # 使用index内置函数求解
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
try:
return haystack.index(needle)
except ValueError:
return -1# 使用find内置函数求解
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
return haystack.find(needle)
