作者介绍：10年大厂数据\经营分析经验，现任大厂数据部门负责人。
会一些的技术：数据分析、算法、SQL、大数据相关、python
欢迎加入社区：码上找工作
作者专栏每日更新：
备注说明：方便大家阅读，统一使用python，带必要注释，公众号 数据分析螺丝钉 一起打怪升级
问题描述
实现 strStr() 函数。给你两个字符串 haystack 和 needle，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1。
说明：
- 当
needle是空字符串时，我们应返回 0 。这与 C 语言的strstr()以及 Java 的indexOf()定义相符。
示例
输入： haystack = "hello", needle = "ll"
输出： 2
输入： haystack = "aaaaa", needle = "bba"
输出： -1
解题思路
实现 strStr() 函数的方法多种多样，包括暴力匹配法、KMP算法、Rabin-Karp 算法等。下面分别简述这些方法：
1. 暴力匹配法
暴力匹配法是最直接的方法，它遍历 haystack 中的每个子串，检查子串是否与 needle 相等。
算法步骤
- 遍历从
0到len(haystack) - len(needle)的每一个起始位置。 - 对每一个起始位置，比较后续的
len(needle)个字符是否与needle相等。
代码实现
这里提供暴力匹配法的实现：
def strStr(haystack: str, needle: str) -> int: """ 实现 strStr() 函数。 Args: haystack (str): 主字符串，从中搜索子字符串。 needle (str): 子字符串，需要在主字符串中找到其第一次出现的位置。 Returns: int: 子字符串在主字符串中第一次出现的索引；如果不存在，则返回 -1。 """ # 特殊情况处理 if not needle: return 0 if not haystack: return -1 # 获取主字符串和子字符串的长度 L, n = len(needle), len(haystack) # 只在主字符串长度减去子字符串长度的范围内搜索 for start in range(n - L + 1): # 检查从start开始的长度为L的子串是否等于needle if haystack[start:start + L] == needle: return start return -1 # 调用函数示例 haystack = "hello" needle = "ll" print(strStr(haystack, needle)) # 输出: 2 haystack = "aaaaa" needle = "bba" print(strStr(haystack, needle)) # 输出: -1
复杂度分析：
- 时间复杂度：O((N-M)M)，其中 N 是
haystack的长度，M 是needle的长度。 - 空间复杂度：O(1)。
2. KMP 算法（Knuth-Morris-Pratt）
算法步骤
KMP算法的核心思想是当发生不匹配时，能够利用已匹配的部分信息，确定模式串的哪个部分应该重新进行匹配，从而避免从头开始匹配。
构建前缀表：
- 前缀表记录了模式串中每个位置之前的子串的前缀与后缀的最长共有元素的长度。
- 这个表用于在发生不匹配时，确定模式串应该回溯到哪个位置重新开始匹配。
搜索过程：
- 使用前缀表来调整模式串的位置，减少不必要的比较。
- 当发生不匹配时，根据前缀表中记录的值调整模式串的位置。
代码实现
def kmp_search(haystack: str, needle: str) -> int: """ 实现 KMP 算法进行字符串搜索。 Args: haystack (str): 主字符串，从中搜索子字符串。 needle (str): 子字符串，需要在主字符串中找到其第一次出现的位置。 Returns: int: 子字符串在主字符串中第一次出现的索引；如果不存在，则返回 -1。 """ if not needle: return 0 if not haystack: return -1 # 构建前缀表 lps = build_lps(needle) i = j = 0 # i 是 haystack 的指针，j 是 needle 的指针 while i < len(haystack): if haystack[i] == needle[j]: i += 1 j += 1 if j == len(needle): return i - j elif j > 0: j = lps[j - 1] else: i += 1 return -1 def build_lps(needle: str) -> list: """ 构建前缀表 (Longest Prefix which is also Suffix table) 用于 KMP 算法。 Args: needle (str): 需要构建前缀表的字符串。 Returns: list: 前缀表。 """ lps = [0] * len(needle) length = 0 # 最长前缀后缀的长度 i = 1 # lps[0] 是 0，从 lps[1] 开始填充表 while i < len(needle): if needle[i] == needle[length]: length += 1 lps[i] = length i += 1 else: if length != 0: length = lps[length - 1] else: lps[i] = 0 i += 1 return lps # 调用函数示例 haystack = "hello" needle = "ll" print(kmp_search(haystack, needle)) # 输出: 2 haystack = "aaaaa" needle = "bba" print(kmp_search(haystack, needle)) # 输出: -1
复杂度分析
- 时间复杂度：O(N+M)，预处理时间为 O(M)，匹配时间为 O(N)。
- 空间复杂度：O(M)。
3. Rabin-Karp 算法
Rabin-Karp 算法是一种高效的字符串搜索算法，特别适用于多模式搜索。它通过计算字符串的哈希值来快速筛选可能的匹配，从而避免在每一步都进行详细的字符比较。
算法步骤
哈希函数：
- 选择一个合适的哈希函数来计算字符串的哈希值。常用的方法是将字符串视为一个大的数值，计算它模一个大素数的值。
计算 needle 的哈希值：
- 计算模式串（
needle）的哈希值。
计算 haystack 子串的哈希值并比较：
- 逐步计算主字符串（
haystack）中每个长度与needle相等的子串的哈希值。 - 如果哈希值匹配，则进行进一步的字符比较以确认完全匹配。
滚动哈希：
- 为了有效计算连续子串的哈希值，使用滚动哈希技术，根据前一个哈希值快速计算下一个哈希值。
def rabin_karp_search(haystack: str, needle: str) -> int: """ 实现 Rabin-Karp 算法进行字符串搜索。 Args: haystack (str): 主字符串，从中搜索子字符串。 needle (str): 子字符串，需要在主字符串中找到其第一次出现的位置。 Returns: int: 子字符串在主字符串中第一次出现的索引；如果不存在，则返回 -1。 """ M, N = len(needle), len(haystack) if M > N: return -1 if not needle: return 0 # 基数和模块数（大素数以减少冲突） base, mod = 256, 997 # 计算needle的哈希值和第一个窗口的哈希值 hash_needle, hash_window = 0, 0 for i in range(M): hash_needle = (hash_needle * base + ord(needle[i])) % mod hash_window = (hash_window * base + ord(haystack[i])) % mod # 如果只有一个字符，直接比较初值 if hash_needle == hash_window: if haystack[:M] == needle: return 0 # 预计算base^(M-1) % mod power_base = 1 for i in range(M - 1): power_base = (power_base * base) % mod # 滚动哈希：遍历剩余的窗口 for i in range(1, N - M + 1): hash_window = (hash_window * base - ord(haystack[i - 1]) * power_base + ord(haystack[i + M - 1])) % mod if hash_window < 0: hash_window += mod if hash_window == hash_needle: # 验证实际字符串是否匹配 if haystack[i:i + M] == needle: return i return -1 # 调用函数示例 haystack = "hello" needle = "ll" print(rabin_karp_search(haystack, needle)) # 输出: 2 haystack = "aaaaa" needle = "bba" print(rabin_karp_search(haystack, needle)) # 输出: -1
复杂度分析：
- 平均时间复杂度：O(N+M)。
- 最坏情况下的时间复杂度：O(NM)，当所有哈希值都冲突时。
- 空间复杂度：O(1)。
总结
下面是对暴力匹配法、KMP算法、以及Rabin-Karp算法在实现 strStr() 函数时的优势、劣势及其时间复杂度和空间复杂度的对比表格，这将帮助在不同场景下选择最适合的方法。
欢迎关注微信公众号 数据分析螺丝钉
