找出字符串中第一个匹配项的下标 图解题解
枚举起点、逐位对，失配立刻换起点——理解朴素匹配，KMP 的跳跃也就顺理成章了。
就像拿一张纸条在一行文字上从左滑动，逐格对齐后从头比每个字符：只要有一个不一样，就把纸条往右挪一格重新比。朴素做法就是这样；KMP 的改进是：失配时不从头比，而是利用纸条自身的重复结构跳到一个更聪明的位置——但原理都是「枚举起点、逐位对」。
这道题到底在问什么
- haystack
- "leetcode"
- needle
- "leeto"
- 输出
- −1
先想最直接的笨办法
为什么这招够用：needle 只可能从文本某个下标 i 处整段对齐开始。所以枚举起点 i，从 needle[0] 起逐位比 needle[k] 与 haystack[i+k]。全比中就是答案，任意一位失配就放弃这个起点、i 右移一位重来。更快的 KMP 失配时不从头比，见末尾模板。（动画第 4 步）
最优解：一步一步想明白
- 3朴素匹配的痛点：在某个起点比到一半失配，就把整个 needle 向右挪一格、从头再逐位比一遍。最坏每个起点都要比 m 次，n 个起点合起来 O(n×m)，重复比较很多。
- 4为什么这招够用：needle 只可能从文本某个下标 i 处整段对齐开始。所以枚举起点 i，从 needle[0] 起逐位比 needle[k] 与 haystack[i+k]。全比中就是答案，任意一位失配就放弃这个起点、i 右移一位重来。更快的 KMP 失配时不从头比，见末尾模板。
- 5needle: leeto · 左端对齐 haystack[0]看下面新出现的一行：那就是模式串 needle 的 l-e-e-t-o，左端整段对齐到文本下标 0，l 标这个起点。接下来就是上下两行逐格比。
- 6needle[0]=l == haystack[0]=l ✓第一位 l 对 l，相等：上行文本格和下行 needle 格一起染绿。指针 i 往右推一格，比下一位。
- 7leet == leet ✓needle 的 l-e-e-t 和文本 0 到 3 的 l-e-e-t 逐位都相等，上下两行前四格全绿，指针 i 推进到 3。看着马上要成功了，再比下一位。
- 8needle[4]=o ≠ haystack[4]=c转折：比到第 5 位，下行 needle 要 o、上行文本是 c，对不上！下行这一格刺眼变红。朴素法很干脆，放弃起点 0，把 needle 整体右移一格，从起点 1 重新比。
- 9i=1，needle[0]=l ≠ haystack[1]=e看下行：整条 needle 往右挪了一格，左端现在压在下标 1。needle[0]=l 对文本下标 1 的 e，第一位就不等，红。这个起点直接淘汰，再右移一格。
- 10i=2，needle[0]=l ≠ haystack[2]=e起点 2：needle 行又右移一格，needle[0]=l 对文本的 e，又是首位不等，红，淘汰，继续右移。
- 11i=3，needle[0]=l ≠ haystack[3]=t起点 3：needle 行右移到下标 3，这是文本里最后一个能完整放下 leeto 的起点。needle[0]=l 对文本下标 3 的 t，仍不等，红，淘汰。
- 12i=4 超过 n−m=3 → 停再右移，needle 行的右端已经探出文本边界——剩下的 c-o-d-e 只有 4 格，放不下 5 格的 leeto。最后可行起点是 n 减 m 等于 3，已经全试过。所有起点都失败，返回 −1。
- 13needle: leeto → code · 滑到 i=4再看一个能命中的：把下行 needle 整段从 leeto 换成 code（注意它现在只有 4 格）。前面起点照样失配，滑到下标 4，needle 的 c 对上文本的 c，绿，继续往右比。
- 14code == code ✓ → return 4下行 code 和上行文本 4 到 7 的 c-o-d-e 逐位全等，上下两行整段染绿，连续比满 m=4 位，匹配成功！返回起点下标 4。这就是命中那一刻：比满 needle 长度就收工。
- 17朴素匹配的灵魂就一句：枚举起点、逐位比、失配就右移一位重来。理解了它，再看 KMP 失配时不从头比、而是按 next 数组跳，就知道它到底省了什么。
- 22把朴素法练熟后，往上一档就是 KMP 的 next 数组：LC459 重复子字符串、LC1392 最长快乐前缀都靠它。想不通时可以问问 AI 助教小欧，或去通关训练里把同类题刷一遍。
⚠️ 容易写错的地方
✗ 错：for i in range(n)，起点枚举到末尾
✓ 对：for i in range(n − m + 1)
起点超过 n−m 时文本剩余长度放不下整个 needle，会越界访问 haystack[i+k]；最后一个合法起点是 n−m
✗ 错：needle 为空时不特判直接进循环
✓ 对：开头加 if m == 0: return 0
约定空模式串匹配在下标 0；不特判时若用 range(n−m+1) 也凑巧对，但显式特判更稳，含义也清楚
✗ 错：内层 while 漏写 k 小于 m 的边界
✓ 对：while k＜m and haystack[i+k]==needle[k]
只写字符相等条件、不限 k 上界，比到 needle 末尾还继续会越界读 needle[k]
完整代码（Python / C++ / Java）
Python
class Solution:
def strStr(self, haystack, needle):
m = len(needle)
if m == 0:
return 0
n = len(haystack)
for i in range(n - m + 1):
k = 0
while k < m and haystack[i + k] == needle[k]:
k += 1
if k == m:
return i
return -1C++
class Solution {
public:
int strStr(string haystack, string needle) {
int m = needle.size();
if (m == 0) return 0;
int n = haystack.size();
for (int i = 0; i + m <= n; i++) {
int k = 0;
while (k < m && haystack[i + k] == needle[k])
k++;
if (k == m) return i;
}
return -1;
}
};Java
class Solution {
public int strStr(String haystack, String needle) {
int m = needle.length();
if (m == 0) return 0;
int n = haystack.length();
for (int i = 0; i + m <= n; i++) {
int k = 0;
while (k < m && haystack.charAt(i + k) == needle.charAt(k))
k++;
if (k == m) return i;
}
return -1;
}
}套路模板 · KMP（失配不回头，背下来）
def kmp(haystack, needle):
m = len(needle)
if m == 0: return 0
nxt = [0] * m # nxt[k]=needle[:k+1] 最长相等前后缀长
j = 0
for i in range(1, m): # 预处理 next 数组
while j and needle[i] != needle[j]: j = nxt[j-1]
if needle[i] == needle[j]: j += 1
nxt[i] = j
j = 0
for i in range(len(haystack)): # 文本指针 i 永不回退
while j and haystack[i] != needle[j]: j = nxt[j-1] # 失配跳
if haystack[i] == needle[j]: j += 1
if j == m: return i - m + 1
return -1int strStr(string haystack, string needle) {
int m = needle.size();
if (m == 0) return 0;
vector<int> nxt(m, 0);
for (int i = 1, j = 0; i < m; i++) {
while (j && needle[i] != needle[j]) j = nxt[j-1];
if (needle[i] == needle[j]) j++;
nxt[i] = j;
}
for (int i = 0, j = 0; i < (int)haystack.size(); i++) {
while (j && haystack[i] != needle[j]) j = nxt[j-1];
if (haystack[i] == needle[j]) j++;
if (j == m) return i - m + 1;
}
return -1;
}public int strStr(String haystack, String needle) {
int m = needle.length();
if (m == 0) return 0;
int[] nxt = new int[m];
for (int i = 1, j = 0; i < m; i++) {
while (j != 0 && needle.charAt(i) != needle.charAt(j)) j = nxt[j-1];
if (needle.charAt(i) == needle.charAt(j)) j++;
nxt[i] = j;
}
for (int i = 0, j = 0; i < haystack.length(); i++) {
while (j != 0 && haystack.charAt(i) != needle.charAt(j)) j = nxt[j-1];
if (haystack.charAt(i) == needle.charAt(j)) j++;
if (j == m) return i - m + 1;
}
return -1;
}复杂度
时间复杂度
O(n×m)
最坏每个起点都比到接近 m 位，共 n−m+1 个起点，n×m 量级
空间复杂度
O(1)
只用 i、k 两个下标，不开额外结构
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 找出字符串中第一个匹配项的下标 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
能不能做到线性 O(n+m)？+
用 KMP。先对 needle 预处理出 next（最长相等前后缀）数组；匹配时文本指针 i 永不回退，失配只把模式指针 j 跳到 next[j−1]，复用已匹配前缀，总体 O(n+m)。
朴素法慢在哪、KMP 省了什么？+
朴素法失配后把已比中的前缀成绩全扔掉、从头重比。KMP 发现已匹配的一段里可能有「前缀=后缀」，可以直接把模式串对齐到那个前缀继续比，不必把文本指针拉回去。
除了 KMP 还有别的线性算法吗？+
有。Rabin-Karp 用滚动哈希，把子串比对降成比哈希值，平均 O(n+m)；BM/Sunday 靠坏字符规则跳得更远，工程里常用。面试通常 KMP 足够。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。