找出字符串中第一个匹配项的下标 图解题解
枚举起点、逐位对，失配立刻换起点——理解朴素匹配，KMP 的跳跃也就顺理成章了。
就像拿一张纸条在一行文字上从左滑动，逐格对齐后从头比每个字符：只要有一个不一样，就把纸条往右挪一格重新比。朴素做法就是这样；KMP 的改进是：失配时不从头比，而是利用纸条自身的重复结构跳到一个更聪明的位置——但原理都是「枚举起点、逐位对」。
这道题到底在问什么
- 输入
- haystack="sadbutsad", needle="sad"
- 输出
- 0 （开头的 "sad" 就匹配上了）
最优解：一步一步想明白
- 3记住这条「逐位对齐比 → 失配就整体右移、从头再比」，下面每一帧都在套它。
- 4文本一字排开，模式串 "ababd" 像一把尺子先放在最左边（下标 0 对齐）。接下来从尺子第一位开始，一格一格往右对比。
- 5尺子放在起点 0：模式串第 0 位 'a' 对上了文本第 0 格的 'a'，这一位相等（标绿），继续往后比下一位。
- 6尺子放在起点 0：模式串第 1 位 'b' 对上了文本第 1 格的 'b'，这一位相等（标绿），继续往后比下一位。
- 7尺子放在起点 0：模式串第 2 位 'a' 对上了文本第 2 格的 'a'，这一位相等（标绿），继续往后比下一位。
- 8尺子放在起点 0：模式串第 3 位 'b' 对上了文本第 3 格的 'b'，这一位相等（标绿），继续往后比下一位。
- 9尺子放在起点 0：模式串第 4 位 'd' 撞上文本第 4 格的 'c'，两者不等（标红）。这个起点废了。
- 10既然起点 0 比不通，就把整把尺子向右挪一格到起点 1，前面对上的都作废、绿色清空，重新从模式串第 0 位开始对比。
- 11尺子放在起点 1：模式串第 0 位 'a' 撞上文本第 1 格的 'b'，两者不等（标红）。这个起点废了。
- 12既然起点 1 比不通，就把整把尺子向右挪一格到起点 2，前面对上的都作废、绿色清空，重新从模式串第 0 位开始对比。
- 13尺子放在起点 2：模式串第 0 位 'a' 对上了文本第 2 格的 'a'，这一位相等（标绿），继续往后比下一位。
- 14尺子放在起点 2：模式串第 1 位 'b' 对上了文本第 3 格的 'b'，这一位相等（标绿），继续往后比下一位。
- 15尺子放在起点 2：模式串第 2 位 'a' 撞上文本第 4 格的 'c'，两者不等（标红）。这个起点废了。
- 16既然起点 2 比不通，就把整把尺子向右挪一格到起点 3，前面对上的都作废、绿色清空，重新从模式串第 0 位开始对比。
- 17尺子放在起点 3：模式串第 0 位 'a' 撞上文本第 3 格的 'b'，两者不等（标红）。这个起点废了。
- 18既然起点 3 比不通，就把整把尺子向右挪一格到起点 4，前面对上的都作废、绿色清空，重新从模式串第 0 位开始对比。
- 19尺子放在起点 4：模式串第 0 位 'a' 撞上文本第 4 格的 'c'，两者不等（标红）。这个起点废了。
- 20既然起点 4 比不通，就把整把尺子向右挪一格到起点 5，前面对上的都作废、绿色清空，重新从模式串第 0 位开始对比。
- 21尺子放在起点 5：模式串第 0 位 'a' 对上了文本第 5 格的 'a'，这一位相等（标绿），继续往后比下一位。
- 22尺子放在起点 5：模式串第 1 位 'b' 对上了文本第 6 格的 'b'，这一位相等（标绿），继续往后比下一位。
- 23尺子放在起点 5：模式串第 2 位 'a' 对上了文本第 7 格的 'a'，这一位相等（标绿），继续往后比下一位。
- 24尺子放在起点 5：模式串第 3 位 'b' 对上了文本第 8 格的 'b'，这一位相等（标绿），继续往后比下一位。
- 25尺子放在起点 5：模式串第 4 位 'd' 对上了文本第 9 格的 'd'，这一位相等（标绿），继续往后比下一位。
- 26从起点 5 一路比到模式串最后一位，全部对上（整段标绿）！这就是 "ababd" 第一次出现的位置，答案返回起始下标 5。
⚠️ 容易写错的地方
✗ 错：起点 i 枚举到 n−1
✓ 对：只枚举到 i + m ≤ n（即 i ≤ n−m）
再往后模式串会越过文本末尾，根本放不下
✗ 错：失配后只把 j 退回 0、i 不动
✓ 对：失配要让起点 i 右移一位，j 重新从 0 开始
同一个起点已经判失败，必须换下一个起点
✗ 错：needle 为空时的返回值搞错
✓ 对：空模式串按约定返回 0
空串在任何位置都「匹配」，下标 0 即可
完整代码（Python / C++ / Java）
Python
def strStr(haystack: str, needle: str) -> int:
n, m = len(haystack), len(needle)
for i in range(n - m + 1): # 枚举每个起点
j = 0
while j < m and haystack[i + j] == needle[j]:
j += 1 # 这一位对上，继续
if j == m: # 全部对上
return i
return -1C++
int strStr(string haystack, string needle) {
int n = haystack.size(), m = needle.size();
for (int i = 0; i + m <= n; i++) { // 枚举起点
int j = 0;
while (j < m && haystack[i + j] == needle[j])
j++; // 对上就往后
if (j == m) return i; // 全对上
}
return -1;
}Java
public int strStr(String haystack, String needle) {
int n = haystack.length(), m = needle.length();
for (int i = 0; i + m <= n; i++) { // 枚举每个起点
int j = 0;
while (j < m &&
haystack.charAt(i + j) == needle.charAt(j))
j++; // 这一位对上，继续
if (j == m) return i; // 全部对上
}
return -1;
}复杂度
时间
O(n·m)
最坏每个起点都要比 m 位，起点有 n−m+1 个
空间
O(1)
只用 i、j 两个下标，不额外开空间
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 找出字符串中第一个匹配项的下标 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
朴素法最坏会有多慢？什么输入能卡到 O(n·m)？+
像 haystack="aaaa…aab"、needle="aaab" 这种：几乎每个起点都能对上前面一长串 a、却在最后一位失配，于是每个起点都白比了近 m 位，总共约 n·m 次比较。
怎么把它优化到线性 O(n+m)？+
用 KMP：先 O(m) 预处理模式串的 next（最长相同前后缀）表；匹配时一旦失配，不把模式串退回起点+1，而是利用 next 表把模式串「滑」到下一个可能匹配的位置，文本指针不回退，总体 O(n+m)。Rabin-Karp（滚动哈希）和 BM 也是常见优化。
为什么很多场景直接用库函数 indexOf / find 就够了？+
库实现通常已对常见输入做了优化，且代码更简洁不易错；面试里被要求手写时才需要展开朴素法或 KMP。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 找出字符串中第一个匹配项的下标 一步步讲透（全站已上线 905 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。