题目
- 给你两个字符串 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 。
法一、KMP
- kmp算法讲的比较清楚的一篇博客：https://blog.csdn.net/qq_62982856/article/details/128003067
- 步骤：根据字串字符构造一个next数组；遍历主串字符串，当匹配失败，查询next数组，定位字串，接着与主串比较
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
def getNext(p):
_next = [0] * (len(p)+1) #初始化next数组
_next[0] = -1
i,j = 0,-1
while i <len (p):
if j==-1 or p[i] == p[j]:#如果j==-1或者两个指针的值相等
i+=1#i前进1步：匹配上了
j+=1#j前进1步:长度加1
_next[i]=j#把长度存进当前next数组
else:#如果两个指针的值不相等
j=_next[j]#回到头部位置
return _next
def kmp(s,p,_next):
i=j=0#i遍历主串j遍历子串
while i<len(s) and j<len(p):
if j==-1 or s[i]==p[j]:#匹配上了
i += 1#主串指针后移1位
j += 1#子串指针后移1位
else:#匹配失效
#主串指针不动，子串指针查next数组进行移动
j=_next[j]
if j==len(p):#字串走完了，每一个字母都匹配
return i-j#返回主串中第一次出现子串的下标
else:
return -1
return kmp(haystack,needle,getNext(needle))
法二、切片
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
if needle in haystack:#先用in判断needle是否在haystack里
for i in range(len(haystack)):#遍历haystack
if haystack[i] == needle[0]:#找到与needle第一个字母相同的地方
if haystack[i:i+len(needle)] == needle:#再对haystack切片needle的长度，如果等于needle就返回答案了，如果不相等，就继续遍历。
return i
else:#如果needle是否在haystack里直接返回-1
return -1
法三、两行
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
try:
return haystack.index(needle)
except:
return -1