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更快，因为它能跳跃式比较（从后往前比）。
这恰恰说明：内置方法是“黑盒”。如果你不了解字符串匹配的底层原理，当遇到复杂问题（比如在超大文本中做模糊匹配、在嵌入式环境中没有现成库）时，你就会束手无策。
一、暴力法慢在哪里？
假设有以下匹配场景：
主串：
haystack = "a b a b a b c"模式串：
needle = "a b a b c"
当逐位比对到第5位时发生冲突：
haystack: a b a b a b c
| | | | X (不匹配：主串是 'a'，模式串是 'c')
needle: a b a b c暴力法的做法：
主串指针回退到第2个字符'b'，模式串重头再来：
haystack: a [b] a b a b c
|
needle: [a] b a b c (第一步就失配，又回退...)
问题所在：前面4位"abab"已经成功比对过了。我们已经明确知道了这4个字符长什么样，完全不需要把主串指针退回去重新看一遍。
二、KMP的核心直觉：最长相等前后缀
在失配发生前，已经成功匹配的子串是"abab"。
观察"abab"的特征：
前缀（包含首字符，不包含尾字符）：
"a"，"ab"，"aba"后缀（包含尾字符，不包含首字符）：
"b"，"ab"，"bab"公共前后缀：两者共有的字符串是
"ab"，其最大长度为2。
KMP 的跳跃逻辑：
既然已匹配部分的末尾2位（"ab"）与开头2位（"ab"）完全一致，那么主串指针可以停在原地不动，直接将模式串向右滑动，让前缀"ab"对齐到刚才的后缀位置：
haystack: a b [a b] a b c
| | ^ (主串停在此处，不回退)
needle: [a b] a b c
滑动后，模式串直接从索引 2（第 3 个字符 'a'）继续比对：
haystack: a b a b [a] b c
| (发现 'a' == 'a'，继续往下走！)
needle: a b [a] b c三、核心工具：next数组（前缀表）
为了让计算机在任意位置失配时都知道该跳到哪，需要提前为模式串needle计算一张表，即next数组（前缀表）。
next[i]的含义是：子串needle[0...i] 中，最长相等前后缀的长度。
以模式串needle = "a b a b c"为例推导：
最终得到next = [0, 0, 1, 2, 0]。
四、代码实现与每一步拆解
KMP包含两个步骤：生成next数组与主串模式串比对。
构建next数组的逻辑
利用双指针：i为后缀末尾指针（从1遍历到末尾），j为最长相等前缀的末尾指针（同时表示当前最长前后缀长度）。
def build_next(needle: str) -> list[int]:
m = len(needle)
next_arr = [0] * m
j = 0 # 前缀末尾位置，也是当前匹配长度
for i in range(1, m):
# 前后缀不匹配时，j 不断回退到上一个公共前后缀的位置
while j > 0 and needle[i] != needle[j]:
j = next_arr[j - 1]
# 前后缀字符相同，前缀长度加 1
if needle[i] == needle[j]:
j += 1
next_arr[i] = j
return next_arr利用next数组进行主串匹配
def kmp_search(haystack: str, needle: str) -> int:
n, m = len(haystack), len(needle)
if m == 0:
return 0
if n < m:
return -1
next_arr = build_next(needle)
j = 0 # 模式串指针
for i in range(n): # i 是主串指针，只递增，绝不回退
# 字符不匹配时，模式串指针根据 next 数组回退
while j > 0 and haystack[i] != needle[j]:
j = next_arr[j - 1]
# 字符匹配，模式串指针后移一位
if haystack[i] == needle[j]:
j += 1
# 模式串全部字符匹配完成
if j == m:
return i - m + 1 # 返回起始匹配索引
return -1