题目描述
给你两个字符串 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 。
解答
class Solution(object):def strStr(self, haystack, needle):""":type haystack: str:type needle: str:rtype: int"""# # 思路一：滑动窗口法# # 初始化两个字符串的长度# m,n=len(needle),len(haystack)# # 定义滑动窗口长度为m，不断移动窗口# for i in range(n-m):# if haystack[i:i+m]==needle:# return i# return -1# # 思路二：find函数# return haystack.find(needle)# 思路三：KMP算法# 首先获取前缀函数def get_prefix_function(pattern):# 记录前缀函数prefix=[0]*len(pattern)# 记录前缀函数取值j=0for i in range(1,len(pattern)):# 匹配失败，回退到前一个匹配的位置 while j > 0 and pattern[i]!=pattern[j]:j=prefix[j-1]# 匹配成功，增加j的值if pattern[i]==pattern[j]:j+=1# 匹配成功，增加前缀长度prefix[i] = j # 记录前缀长度return prefixdef kmp_search(pattern,text):prefix=get_prefix_function(pattern)n,m=len(text),len(pattern)j=0for i in range(n):# 匹配不成功则一直回退while j>0 and pattern[j]!=text[i]:j=prefix[j-1]# 匹配成功则增加j的值if pattern[j]==text[i]:j+=1# 记录第一次完全匹配的位置if j==m:return i-m+1# 如果没有完全匹配则返回-1return -1# 直接返回结果return kmp_search(needle,haystack)思路一，滑动窗口法：滑动窗口法是一种暴力匹配的改进。通过设置一个固定大小（等于模式串长度）的窗口，从文本串的起始位置逐步滑动到末尾，每次截取与模式串长度相同的子串进行比较。如果找到匹配子串，则返回其起始位置；如果滑动到末尾都没有找到匹配，则返回 -1。这种方法简单直观，但时间复杂度为 O((n−m)⋅m)，在大规模输入中性能较为有限。
思路二，使用内置 find 函数：Python 提供了内置的 find 函数，直接在文本串中寻找模式串的起始位置。其内部实现已优化，可高效完成匹配操作。这当然是一种非常取巧的方法，使用这一方法时，只需调用 haystack.find(needle) 即可返回模式串在文本串中的起始位置，若不存在则返回 -1。它是最简洁和直观的实现，但具体性能依赖于底层实现。
思路三，KMP 算法：KMP 算法是一种高效的字符串匹配算法，利用模式串的部分匹配信息避免重复比较，时间复杂度为 O(n+m)。它通过构造模式串的前缀函数表（prefix），在匹配过程中通过回退模式串的索引实现高效跳跃，减少了暴力匹配中的重复操作。KMP 更适合需要处理大量字符串匹配的问题。尽管实现较复杂，但它在性能上相较于滑动窗口法更加优越。
知识拓展：KMP算法
🎯 什么是 KMP 算法？
KMP（Knuth-Morris-Pratt）算法是一个用来解决 字符串匹配问题 的神器。比如你想在一本书（text）中找出一个词语（pattern）出现的地方，KMP 就能帮你快速搞定！
📜 KMP算法的主要特点：
- 不像暴力匹配一样，每次匹配失败后重新开始。
- 它可以聪明地利用之前的匹配信息，把模式串“往前跳”，避免重复信息的比较。
- 时间复杂度是 O(n+m)，是一种非常高效的匹配算法。
😭 KMP 是怎么解决暴力匹配的痛点？
想象一下：
- 你有一个模式串
pattern = "ababc"，要在文本串text = "ababaabc"中找到它。 - 用暴力法，当匹配到
ababa时，发现第 6 个字符不对，就会笨笨地 回到头部重新开始。
KMP 会想：“兄弟，前几个字符我们明明已经对上了，没必要重新比呀！这不是浪费时间吗？”于是，它在失配后 根据前缀表（prefix table），聪明地跳到可能的位置继续匹配。那么可能的位置在哪呢？这个时候就需要前缀表的帮助了。
🛠 核心思想：前缀表（Prefix Table）
前缀表是 KMP 的灵魂！它告诉我们，模式串的哪些部分已经可以重复利用，从而避免重新比较。而所谓前缀，实际上就是子串的开头部分，反之后缀则是子串的结尾部分，前缀表的值就是模式串的前缀和后缀相同的最大长度。
比如，pattern = "ababc"，它的前缀表构造如下：
pattern: a b a b c
prefix: 0 0 1 2 0
前缀表的构建
- 遍历模式串，比较字符是否匹配。
- 如果匹配，前缀长度
j+1。 - 如果不匹配，回退到上一个匹配的位置（
prefix[j-1]）。
📈 KMP 的匹配过程
匹配时：
- 字符匹配：模式串和文本串的指针都往后移。
- 字符不匹配：模式串根据前缀表跳到下一个可能匹配的位置，文本串指针不动。
用刚才的 pattern = "ababc" 和 text = "ababaabc" 来走一遍：
text: a b a b a a b c
pattern: a b a b c↑ ↑ ↑ ↑ ↑
匹配到第 5 个字符，发现失配，前缀表告诉我们跳到第 3 个位置，即：
text: a b a b a a b c
pattern: a b a b c↑ ↑ ↑
KMP 就这么避免了重复比较，一路高效前进。
🔧 实现代码（Python版）
下面是这道题目中 KMP 的完整实现：
def kmp_search(text, pattern):def get_prefix_function(pattern):prefix = [0] * len(pattern)j = 0for i in range(1, len(pattern)):while j > 0 and pattern[i] != pattern[j]:j = prefix[j - 1]if pattern[i] == pattern[j]:j += 1prefix[i] = jreturn prefixprefix = get_prefix_function(pattern)j = 0for i in range(len(text)):while j > 0 and text[i] != pattern[j]:j = prefix[j - 1]if text[i] == pattern[j]:j += 1if j == len(pattern):return i - len(pattern) + 1return -1
✨ 一句话总结
KMP 算法的关键在于失配时它会回忆之前的匹配情况，聪明地跳到下一个可能的位置继续找，从不浪费时间。
记住它的两个关键点：
- 构建前缀表（Prefix Table）。
- 利用前缀表在匹配过程中跳跃指针。
希望这次分享让你对 KMP 算法有了更深入的理解！
感谢阅读，希望对你有所帮助~
