题目描述
返回模式串 needle 在文本 haystack 中第一次出现的下标，没有返回 −1。
haystack = "aabaabaaf"
needle = "aabaaf"
输出 = 3
思路解析
暴力法每次失配，就把文本指针拉回去、模式串从头再对一遍——大量重复比较。KMP 的突破：失配时，已经匹配上的那段前缀里藏着信息，能让模式串直接滑到该滑的地方，文本不用回退。
next[k] 就是模式串前 k 个字符里“最长的、既是前缀又是后缀”的长度。失配时不从头来，而是让模式串指针 j 跳到 next[j-1]——相当于把模式串向右滑、复用已匹配的部分。文本指针 i 一路向前不回头。
文本 i 前进，逐位和模式串比：文本(下方)从下标 3 起和模式串 "aabaaf" 对齐：a-a、a-a 连续匹配(绿色)，i 走到 4、模式串 j 走到 2。
在某处失配：继续比到文本下标 5(b) 和模式串第 5 位(f)，不相等，失配。暴力会把 i 拉回去；KMP 不——它查 next，让模式串 j 跳回去。
KMP · 文本不退，模式串滑：j 跳到 next[j-1](利用 "aa" 这个公共前后缀)，模式串整体右滑、复用已匹配的 "aa"。文本指针 i 停在 5 不回退，从这里继续比。
继续直到完全匹配：文本不回退地继续推进，最终模式串从下标 3 起完整匹配 "aabaaf"，返回 3。
KMP 的灵魂是 next 数组——它把“已经匹配上的前缀里的前后缀信息”提前算好，失配时直接复用，避免文本指针回退造成的重复比较。理解 next 是理解 KMP 的关键。
参考代码（Python）
Python
1nxt = build_next(needle) # 预处理 next 数组
2j = 0 # 模式串指针
3for i in range(len(haystack)): # 文本指针 i 不回退
4 while j > 0 and haystack[i] != needle[j]:
5 j = nxt[j-1] # 失配: 模式串回跳
6 if haystack[i] == needle[j]: j += 1 # 匹配: 前进
7 if j == len(needle): return i - j + 1 # 全匹配
8return -1复杂度分析
- 时间复杂度：O(n + m) —— 文本 n、模式 m 各扫一遍
- 空间复杂度：O(m) —— next 数组
套路模板
记住骨架：next 的构建就是“模式串自己和自己做 KMP 匹配”，和主匹配逻辑一模一样。把这两段对照着背，KMP 就拿下了。
Python
1def build_next(p):
2 nxt = [0] * len(p); j = 0
3 for i in range(1, len(p)):
4 while j > 0 and p[i] != p[j]: # 和匹配主逻辑同构
5 j = nxt[j-1]
6 if p[i] == p[j]: j += 1
7 nxt[i] = j # 前 i+1 个的最长公共前后缀
8 return nxt易错点
- ❌ 失配时把文本指针 i 回退 → ✅ i 只前进，回退的是模式串 j（文本不回退正是 KMP 的精髓与提速点）
- ❌ next 含义记混 → ✅ next[k]=前 k 个的最长相等前后缀长度（它决定失配后 j 跳到哪）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。