暴力双重循环
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
"""
在 haystack 中寻找 needle 第一次出现的位置，找不到返回 -1。
题目保证 1 <= len(haystack), len(needle) <= 10^4
"""
# n: 主串长度，m: 模式串长度
n = len(haystack)
m = len(needle)
# 如果 needle 比 haystack 还长，必不可能匹配
if m > n:
return -1
# 外层循环：枚举“匹配起点” i
# i 最大只能到 n - m（含），因为再往后剩余长度不足 m
# 所以 range(n - m + 1)
for i in range(n - m + 1):
# 内层指针 j：表示 needle 当前匹配到的位置
j = 0
# 逐个字符比较：
# haystack 的第 i+j 个字符 与 needle 的第 j 个字符
# 只要相同就继续推进 j
while j < m and haystack[i + j] == needle[j]:
j += 1
# 如果 j 走到了 m，说明 needle[0..m-1] 全部匹配成功
# 当前起点 i 就是第一个匹配下标（因为 i 是从小到大枚举的）
if j == m:
return i
# 否则当前 i 匹配失败，外层 for 会自动尝试下一个 i
# 所有起点都试过仍未匹配
return -1Python内置方法
def strStr(haystack: str, needle: str) -> int:
return haystack.find(needle)KMP算法
既然Python有现成的haystack.find(needle)（底层还是C语言实现的，运行速度极快），为什么我们还要费力去学、去手写KMP呢？
答案只有一句话：KMP是给“人”学的算法知识，而find()是给“计算机”用的工具。
大厂面试时，面试官想看到的是你如何设计匹配逻辑、如何处理边界条件、如何优化时间复杂度。
如果你直接写find()，面试官通常会追问：“如果让你自己实现这个find方法，不允许用内置函数，你怎么做？” 这就是KMP登场的时机。
Python内置find()底层用的也不是KMP，这是一个非常有趣的冷知识：CPython（标准Python解释器）的字符串查找底层，并不使用KMP算法。它主要使用的是Boyer-Moore-Horspool（BMH）算法或Two-Way 算法（一种更先进的线性算法）。
BMH算法在某些情况下比KMP更快，因为它能跳跃式比较（从后往前比）。
这恰恰说明：内置方法是“黑盒”。如果你不了解字符串匹配的底层原理，当遇到复杂问题（比如在超大文本中做模糊匹配、在嵌入式环境中没有现成库）时，你就会束手无策。