题目
给你两个字符串 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算法,是我见过代码讲的最清楚的了(点赞)。
我们的目标是文本串中找到模式串,并返回它在文本串中出现的首位值。
主要思路是第一步求出模式串的next数组(其实也就是模式串最大公共前后缀长度值)第二步是利用next数组优化字符串匹配过程,从而降低复杂度。
最后只要是字符串匹配相关得算法题,都可以用kmp优化,相比暴力得o(n*m)时间复杂度,KMP将时间复杂度降为了o(m+n),简直不要太快,强烈推荐掌握!
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
# 目标是从文本串中找到模式串是否出现过,如果出现则返回出现的第一个位置
# 1.得到模式串的next数组(也就是前缀表)
def get_next(s):
next = [0]*len(s)
j = -1
next[0] = j
# i指向后缀的结束位置(包含结束位置),j指向前缀的结束位置(包含结束位置)
for i in range(1,len(next)):
# 前后缀不相同,将j指针回溯,直到找到与后缀相同的字符或者j==-1
while j>=0 and s[j+1]!=s[i]:
j = next[j]
# 前后缀相同,i和j同时往后移动,i的移动在for循环中
if s[j+1] == s[i]:
j += 1
next[i] = j
return next
# 2.通过next数组优化字符串匹配过程
next = get_next(needle)
j = -1
for i in range(len(haystack)):
# 文本串与模式串不匹配
while j>=0 and haystack[i]!=needle[j+1]:
j = next[j]
# 文本串与模式串匹配,i和j都右移,其中i的右移包含在for循环中了
if haystack[i] == needle[j+1]:
j += 1
# 模式串已经匹配完毕,返回即可
if j == len(needle)-1:
return i-len(needle)+1
return -1