找出字符串中第一个匹配项的下标

难度：中等
给你两个字符串 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 。

解法一、BF算法

思路：
逐字符地进行匹配(比较 A[i]A[i]A[i] 和 B[j]B[j]B[j])，如果当前字符匹配成功( A[i]==B[j]A[i]==B[j]A[i]==B[j] )，就匹配下一个字符(++i，++j++i，++j++i，++j)，如果失配，iii 回溯，jjj 置为000 (i=i−j+1，j=0i=i-j+1，j=0i=i−j+1，j=0)。

时间复杂度：O(m∗n)O(m*n)O(m∗n)，与主串和模式串的长度都正相关
空间复杂度：O(1)O(1)O(1)

class Solution:def strStr(self, haystack: str, needle: str) -> int:needle_length = len(needle)for i in range(len(haystack) - needle_length + 1):for x, y in zip(haystack[i:i+needle_length], needle):if x != y:break else:return ireturn -1

解法二、RK算法

思路：
对于给定文本串 haystackhaystackhaystack 与模式串 needleneedleneedle，通过滚动哈希算快速筛选出与模式串 needleneedleneedle 不匹配的文本位置，然后在其余位置继续检查匹配项。此处采用 ordordord 函数代替hash，数字较小便于计算。
时间复杂度： O(n)O(n)O(n)。其中文本串 haystackhaystackhaystack 的长度为 nnn，模式串 needleneedleneedle 的长度为 mmm。
空间复杂度： O(1)O(1)O(1)。

class Solution:def strStr(self, haystack: str, needle: str) -> int:needle_length = len(needle)needle_sum = sum(ord(i) for i in needle)haystack_sum = sum(ord(i) for i in haystack[:needle_length])for i in range(len(haystack) - needle_length + 1):if i != 0:haystack_sum = haystack_sum - ord(haystack[i-1]) + ord(haystack[i+needle_length-1])if needle_sum == haystack_sum:for x, y in zip(haystack[i:i+needle_length], needle):if x != y:break else:return ireturn -1

解法三、BM算法

思路：
记 haystackhaystackhaystack 为 TTT，needlepneedlepneedlep 为 ppp，对于给定文本串 TTT 与模式串 ppp，先对模式串 ppp 进行预处理。然后在匹配的过程中，当发现文本串 TTT 的某个字符与模式串 ppp 不匹配的时候，根据启发策略，能够直接尽可能地跳过一些无法匹配的情况，将模式串多向后滑动几位。

BMBMBM 算法具体步骤如下：

1. 计算出文本串 TTT 的长度为 nnn，模式串 ppp 的长度为 mmm。
2. 设置左指针为 leftleftleft，两个文本串长度差为 differdifferdiffer，differdifferdiffer同时为 leftleftleft 最大移动步长，如果 left<=differleft<=differleft<=differ，则进入循环体，采用 BMBMBM 算法更新 leftleftleft，步骤如下：
   • 如果文本串对应位置 T[i+j]T[i + j]T[i+j] 上的字符与 p[j]p[j]p[j] 相同，则继续比较前一位字符。
     1. 如果模式串全部匹配完毕，则返回 TrueTrueTrue。
   • 如果文本串对应位置 T[i+j]T[i + j]T[i+j] 上的字符与 p[j]p[j]p[j] 不相同，则：
     1. 根据坏字符位置表计算出在「坏字符规则」下的移动距离 bad_characters_movebad\_characters\_movebad_characters_move。
     2. 根据好后缀规则后移位数表计算出在「好后缀规则」下的移动距离 good_suffix_movegood\_suffix\_movegood_suffix_move。
     3. 返回两种移动距离的最大值，即 max(bad_characters_move，good_suffix_move)max(bad\_characters\_move， good\_suffix\_move)max(bad_characters_move，good_suffix_move)。
3. 如果移动到末尾也没有找到匹配情况，则返回 -1。如果匹配到了，则返回 leftleftleft。

时间复杂度： O(n/m)O(n/m)O(n/m)，最坏O(m∗n)O(m*n)O(m∗n)
空间复杂度： O(suffix)O(suffix)O(suffix)，suffixsuffixsuffix 为后缀长度，小于模式串 ppp。

class Solution:def bm(self, str1, str2, str2_length):for i in range(str2_length-1, -1, -1):if str1[i] != str2[i]:# 坏字符bad_characters_move = i + 1suffix = str1[i+1:]for j in range(i-1, -1, -1):if str2[j] == str1[i]:bad_characters_move = i - jbreak# 好后缀good_suffix_move = 0suffix_length = len(suffix)if suffix_length:for j in range(i, -suffix_length, -1):if str2[j-suffix_length+1:j+1] == suffix:good_suffix_move = i - j + 1breakreturn max(bad_characters_move, good_suffix_move)else:return Truedef strStr(self, haystack: str, needle: str) -> int:needle_length = len(needle)haystack_length = len(haystack)differ = haystack_length - needle_lengthleft = 0while left <= differ:move = self.bm(haystack[left:left+needle_length], needle, needle_length)if move is True:return leftleft += movereturn -1

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string