题目描述
返回模式串 needle 在文本 haystack 中第一次出现的下标，找不到返回 −1。
思路解析
朴素匹配的痛点：在某个起点比到一半失配，就把整个 needle 向右挪一格、从头再逐位比一遍。最坏每个起点都要比 m 次，n 个起点合起来 O(n×m)，重复比较很多。
为什么这招够用：模式串只可能从文本的某个下标 j 处「整段对齐」开始。所以枚举起点 j，从 needle[0] 起逐位比 needle[k] 与 haystack[j+k]；全比中就是答案，任意一位失配就放弃这个起点、j 右移一位重来。（更快的 KMP 失配时不从头比，见末尾模板。）
起点 j=0 · 对齐：把 needle 的左端对齐到文本下标 0（l 标起点）。cur 是当前比较位，从这里逐位向右比。
起点 0 · 前 4 位都对上：needle 的 l-e-e-t 和文本 0..3 的 l-e-e-t 逐位都相等（绿色），cur 推进到 3。看着马上要成功了——再比下一位。
起点 0 · 第 5 位失配（负例）：转折（负例）：比到第 5 位，needle 要 o、文本是 c，对不上！朴素法的反应很干脆：放弃起点 0，把 needle 整体右移一位，从起点 1 重新逐位比。
起点 j=1 · 首位就失配：右移到起点 1：needle[0]=l 对文本下标 1 的 e，第一位就不等。这个起点直接淘汰，再右移一位。
起点 j=2 · 首位失配：起点 2：needle[0]=l 对文本的 e，又是首位不等，淘汰，继续右移。
起点 j=3 · 首位失配：起点 3：needle[0]=l 对文本下标 3 的 t，仍不等，淘汰。
起点越界 · 没有更多起点了：文本剩下的长度已经不够放下整个 "leeto"（最后可行起点是 n−m=3，已试完）。所有起点都失败，返回 −1。
答案 · 没找到：每个起点都对不齐，"leeto" 不是 "leetcode" 的子串，返回 −1。若把 needle 换成 "code"，会在起点 4 完整匹配、返回 4。
朴素匹配的灵魂就一句：枚举起点、逐位比、失配就右移一位重来。理解了它，再看 KMP「失配时不从头比、而是按 next 数组跳」就知道它到底省了什么。
参考代码（Python）
1def strStr(haystack, needle):
2 n, m = len(haystack), len(needle)
3 if m == 0: return 0 # 空串约定返回 0
4 for j in range(n - m + 1): # 枚举起点，最后一个是 n−m
5 k = 0
6 while k < m and haystack[j + k] == needle[k]: # 逐位比
7 k += 1
8 if k == m: return j # 全比中 → 命中
9 return -1 # 所有起点都失配复杂度分析
- 时间复杂度：O(n×m) —— 最坏每个起点都比到接近 m 位，n−m+1 个起点
- 空间复杂度：O(1) —— 只用 j、k 两个下标，不开额外结构
套路模板
KMP 的关键升级：失配时不把文本指针 i 拉回去、也不把 needle 从头比，而是让模式串指针 j 跳到 next[j−1]，复用已匹配的前后缀。文本一路向前，整体 O(n+m)。
1def build_next(p): # next[k]=前 k 个最长相等前后缀长度
2 nxt = [0] * len(p); j = 0
3 for i in range(1, len(p)):
4 while j and p[i] != p[j]: j = nxt[j-1]
5 if p[i] == p[j]: j += 1
6 nxt[i] = j
7 return nxt
8nxt = build_next(needle); j = 0
9for i in range(len(haystack)): # 文本指针 i 永不回退
10 while j and haystack[i] != needle[j]: j = nxt[j-1] # 失配跳
11 if haystack[i] == needle[j]: j += 1
12 if j == len(needle): return i - j + 1易错点
- 错误写法：for j in range(n)（起点枚举到末尾） → 正确写法：for j in range(n − m + 1)（起点超过 n−m 时文本剩余长度放不下整个 needle，会越界访问 haystack[j+k]；最后一个合法起点是 n−m）
- 错误写法：needle 为空时不特判直接进循环 → 正确写法：开头加 if m == 0: return 0（约定空模式串匹配在下标 0；不特判会让边界判断变绕甚至出错）
- 错误写法：（KMP）失配时把文本指针 i 回退 → 正确写法：i 只前进，回退的是模式串 j = next[j−1]（文本不回退正是 KMP 把 O(n×m) 降到 O(n+m) 的命门，回退就退化成朴素法）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。