力扣热题100实战 | 第28期：找出字符串中第一个匹配项的下标——从暴力到KMP的跃迁

力扣热题100实战 | 第28期：找出字符串中第一个匹配项的下标——从暴力到KMP的跃迁

• • 前言
  • 一、题目：在主串中找子串
  • • 关键点解读
  • 二、第一反应：暴力匹配法（直观但低效）
  • • 核心思想
    • 图解流程
    • 代码实现
    • 复杂度分析
    • 这段代码的问题在哪？
  • 三、KMP算法核心思想：利用已匹配信息
  • • 3.1 为什么需要KMP？
    • 3.2 前缀和后缀的概念
    • 3.3 最长公共前后缀
    • 3.4 KMP的匹配过程
  • 四、next数组的构建
  • • 4.1 next数组的含义
    • 4.2 构建过程图解
    • 4.3 代码实现
  • 五、KMP完整代码实现
  • • 5.1 匹配过程代码
    • 5.2 代码解析
    • 5.3 复杂度分析
  • 六、暴力 vs KMP：巅峰对决
  • • 面试建议
  • 七、细节剖析：面试官真正关心的问题
  • • Q1：KMP为什么能保证主串指针永不回退？
    • Q2：next数组构建中的 `while (j > 0 && needle.charAt(i) != needle.charAt(j))` 是什么意思？
    • Q3：为什么需要单独处理空字符串？
    • Q4：如果子串长度大于主串，直接返回-1，这是优化吗？
    • Q5：KMP算法有什么局限性？
  • 八、面试官追问进阶版
  • • 追问1：如何用Rabin-Karp算法（滚动哈希）解决本题？
    • 追问2：如果要求找出所有匹配的位置，而不是第一个，代码怎么改？
    • 追问3：如何优化KMP的空间复杂度？
  • 九、实际开发：这道题到底有什么用？
  • • 场景1：文本编辑器的查找功能
    • 场景2：搜索引擎的关键词匹配
    • 场景3：代码编辑器的语法高亮
    • 场景4：日志分析系统
    • 场景5：生物信息学中的DNA序列匹配
  • 十、总结：从一道题到一类题
  • 附录：思考题

字符串匹配是计算机科学中最基础也最经典的问题之一。从暴力解法的直观，到KMP的精巧，这不仅是算法的进阶，更是思维的跃迁——学会利用已匹配部分的信息，避免重复劳动。

前言

你好，我是@礼拜天没时间。

上一期我们学习了“移除元素”（第27题），掌握了双指针在数组原地操作中的灵活运用。这一期，我们进入字符串专题，来解一道看似简单却蕴含经典思想的题目——找出字符串中第一个匹配项的下标（LeetCode 第28题）。

这道题在力扣上被标记为“简单”，但它的简单仅限于暴力解法。真正的价值在于，它是理解KMP算法的最佳入门案例——一个让无数初学者头疼，却又无比精妙的字符串匹配算法。

今天，我希望能带你从最直观的暴力匹配出发，分析它的低效原因，然后一步步推导出KMP的核心思想，让你真正理解“利用已匹配信息”这一精髓。

一、题目：在主串中找子串

先看题目描述（LeetCode 第28题）：

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

示例 1：

输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。第一个匹配项的下标是 0，所以返回 0。

示例 2：

输入：haystack = "leetcode", needle = "leeto"
输出：-1
解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1。

关键点解读

二、第一反应：暴力匹配法（直观但低效）

当我第一次看到这道题，我的第一反应是：枚举主串中的每个可能起点，逐个字符与子串比较 。

核心思想

图解流程

以 haystack = "sadbutsad", needle = "sad" 为例：

第1轮：i=0
sadbutsad
↑
sad → 完全匹配 ✅ 返回0

第2轮：i=1（不需要，因为第1轮已成功）

以 haystack = "mississippi", needle = "issip" 为例：

第1轮：i=0
mississippi
↑
issip → m vs i ❌ 失败

第2轮：i=1
mississippi
↑
issip → i vs i ✅，继续
s vs s ✅，继续
s vs s ✅，继续
i vs i ✅，继续
s vs p ❌ 失败

第3轮：i=2
mississippi
↑
issip → s vs i ❌ 失败

… 直到找到匹配位置

代码实现

class Solution {
public int strStr(String haystack, String needle) {
int n = haystack.length(), m = needle.length();

// 空字符串处理
if (m == 0) return 0;

// 枚举主串的每个可能起点
for (int i = 0; i <= n – m; 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 个字符
• 空间复杂度：O(1) —— 只用了常数变量

这段代码的问题在哪？

三、KMP算法核心思想：利用已匹配信息

3.1 为什么需要KMP？

观察下面的匹配过程 ：

haystack: a b e a b a b e a b f
↑
needle: a b e a b f
↑

当匹配到第6个字符时（f vs a），发现不匹配。暴力法会这样做：

但这样浪费了什么？我们已经知道前面的 “abeab” 是匹配的，这部分信息完全可以用来加速下一次匹配 。

3.2 前缀和后缀的概念

要理解KMP，首先需要理解两个概念 ：

• 前缀：字符串中不包含最后一个字符的所有以第一个字符开头的连续子串
• 后缀：字符串中不包含第一个字符的所有以最后一个字符结尾的连续子串

例如对于字符串 “abab”：

• 前缀："a", "ab", "aba"
• 后缀："b", "ab", "bab"

3.3 最长公共前后缀

KMP的核心是：对于子串的每个位置，找到已匹配部分的最长公共前后缀 。

以 “ababf” 为例，当匹配到 f 失败时，已匹配部分是 “abab”：

• “abab” 的前缀："a", "ab", "aba"
• “abab” 的后缀："b", "ab", "bab"
• 最长公共前后缀："ab"（长度为2）

这意味着什么？当我们从 “ababf” 的 f 处失败时，我们可以直接跳转到 “ab” 的下一个位置继续匹配，因为 “ab” 这部分已经确认是匹配的 。

3.4 KMP的匹配过程

还是上面那个例子 ：

第1次匹配到f失败时：
haystack: a b e a b a b e a b f
needle: a b e a b f
↑ 失败

利用已匹配的"abeab"的最长公共前后缀"ab"：
needle跳转到：
a b e a b f
↑ (从第三个字符继续)

继续匹配…

这样，主串指针永远不回退，只移动子串指针，大大提高了效率 。

四、next数组的构建

4.1 next数组的含义

next[i] 表示：在子串 needle[0…i] 这个子串中，最长公共前后缀的长度 。

例如 needle = "ababf"：

• next[0] = 0（单个字符没有公共前后缀）
• next[1] = 0（“ab” 的前缀 “a” ≠ 后缀 “b”）
• next[2] = 1（“aba” 的公共前后缀 “a”）
• next[3] = 2（“abab” 的公共前后缀 “ab”）
• next[4] = 0（“ababf” 无公共前后缀）

4.2 构建过程图解

以 needle = "aaabbab" 为例：

4.3 代码实现

private int[] buildNext(String needle) {
int m = needle.length();
int[] next = new int[m];
next[0] = 0; // 第一个字符没有公共前后缀

// j 指向前缀的末尾，i 指向后缀的末尾
for (int i = 1, j = 0; i < m; i++) {
// 当字符不匹配时，j 回退到 next[j-1]
while (j > 0 && needle.charAt(i) != needle.charAt(j)) {
j = next[j – 1];
}
// 字符匹配，j 向前移动
if (needle.charAt(i) == needle.charAt(j)) {
j++;
}
next[i] = j;
}
return next;
}

这种实现方式的时间复杂度是 O(m)，空间复杂度 O(m) 。

五、KMP完整代码实现

5.1 匹配过程代码

class Solution {
public int strStr(String haystack, String needle) {
int n = haystack.length(), m = needle.length();

// 空字符串处理
if (m == 0) return 0;
if (n < m) return –1;

// 构建next数组
int[] next = buildNext(needle);

// 匹配过程
for (int i = 0, j = 0; i < n; i++) {
// 字符不匹配时，j 根据next数组回退
while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {
j = next[j – 1];
}
// 字符匹配，j向前移动
if (haystack.charAt(i) == needle.charAt(j)) {
j++;
}
// 完全匹配成功
if (j == m) {
return i – m + 1;
}
}

return –1;
}

private int[] buildNext(String needle) {
int m = needle.length();
int[] next = new int[m];
next[0] = 0;

for (int i = 1, j = 0; i < m; i++) {
while (j > 0 && needle.charAt(i) != needle.charAt(j)) {
j = next[j – 1];
}
if (needle.charAt(i) == needle.charAt(j)) {
j++;
}
next[i] = j;
}
return next;
}
}

5.2 代码解析

5.3 复杂度分析

• 时间复杂度：O(n + m) —— 构建next O(m)，匹配过程 O(n)
• 空间复杂度：O(m) —— 存储next数组

六、暴力 vs KMP：巅峰对决

面试建议

优先掌握暴力解法，因为：

KMP作为进阶技能：在写完暴力解法后，可以主动提出“这道题还可以用KMP算法优化到O(n+m)”，然后简要介绍核心思想，展示你的知识广度 。

七、细节剖析：面试官真正关心的问题

Q1：KMP为什么能保证主串指针永不回退？

答案：因为next数组记录了已匹配部分的信息。当发生失配时，我们可以通过next数组知道子串应该跳转到哪个位置继续匹配，而不需要重新检查已经匹配过的字符 。

Q2：next数组构建中的 while (j > 0 && needle.charAt(i) != needle.charAt(j)) 是什么意思？

答案：这是KMP最精妙的部分。当当前字符不匹配时，我们需要回退到更短的公共前后缀，继续尝试匹配。这个过程可能重复多次，直到找到匹配的位置或者回到起点 。

Q3：为什么需要单独处理空字符串？

答案：这是题目约定，空字符串被视为在任何字符串的起始位置匹配。Java的 indexOf 方法也是如此实现 。

Q4：如果子串长度大于主串，直接返回-1，这是优化吗？

答案：是的，这是一个简单的剪枝优化。如果主串长度都不够，肯定无法匹配，可以直接返回-1，避免后续无意义的计算。

Q5：KMP算法有什么局限性？

答案：KMP的主要局限性是：

八、面试官追问进阶版

追问1：如何用Rabin-Karp算法（滚动哈希）解决本题？

思路：Rabin-Karp用哈希值比较子串，可以在O(n)平均时间内完成匹配 。

public int strStr(String haystack, String needle) {
int n = haystack.length(), m = needle.length();
if (m == 0) return 0;
if (n < m) return –1;

// 计算needle的哈希值
int needleHash = 0;
for (int i = 0; i < m; i++) {
needleHash = needleHash * 26 + (needle.charAt(i) – 'a');
}

// 计算第一个窗口的哈希值
int hayHash = 0;
for (int i = 0; i < m; i++) {
hayHash = hayHash * 26 + (haystack.charAt(i) – 'a');
}

if (hayHash == needleHash && checkEqual(haystack, 0, needle)) {
return 0;
}

// 滑动窗口
int power = (int) Math.pow(26, m – 1);
for (int i = 1; i <= n – m; i++) {
// 更新哈希值：去掉前一个字符，加上新字符
hayHash = (hayHash – (haystack.charAt(i – 1) – 'a') * power) * 26
+ (haystack.charAt(i + m – 1) – 'a');

if (hayHash == needleHash && checkEqual(haystack, i, needle)) {
return i;
}
}

return –1;
}

private boolean checkEqual(String haystack, int start, String needle) {
for (int i = 0; i < needle.length(); i++) {
if (haystack.charAt(start + i) != needle.charAt(i)) {
return false;
}
}
return true;
}

追问2：如果要求找出所有匹配的位置，而不是第一个，代码怎么改？

思路：在匹配成功时，记录位置并继续搜索，而不是直接返回。

public List<Integer> findAll(String haystack, String needle) {
List<Integer> result = new ArrayList<>();
int n = haystack.length(), m = needle.length();
if (m == 0) return result;

int[] next = buildNext(needle);

for (int i = 0, j = 0; i < n; i++) {
while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {
j = next[j – 1];
}
if (haystack.charAt(i) == needle.charAt(j)) {
j++;
}
if (j == m) {
result.add(i – m + 1);
j = next[j – 1]; // 继续搜索下一个匹配
}
}

return result;
}

追问3：如何优化KMP的空间复杂度？

思路：next数组的空间复杂度O(m)是必须的，但可以通过压缩存储来减少。不过对于本题的数据范围，O(m)完全可以接受。

九、实际开发：这道题到底有什么用？

很多读者会问：“字符串匹配，实际工作中哪用得到？”

其实它的思想无处不在：

场景1：文本编辑器的查找功能

当你在Word或VS Code中按Ctrl+F查找关键词时，背后就是字符串匹配算法在运行 。

场景2：搜索引擎的关键词匹配

搜索引擎需要在海量文档中快速匹配用户输入的关键词，高效的字符串匹配算法至关重要。

场景3：代码编辑器的语法高亮

IDE需要识别代码中的关键字、字符串字面量等，这离不开字符串匹配。

场景4：日志分析系统

在分析服务器日志时，需要查找特定的错误模式或访问路径，KMP可以帮助快速定位。

场景5：生物信息学中的DNA序列匹配

在基因测序中，需要在长DNA序列中查找特定的基因片段，字符串匹配算法是基础工具 。

十、总结：从一道题到一类题

回顾一下，我们从找出字符串中第一个匹配项的下标学到了什么：

力扣热题100的第二十八题，不是为了难住你，而是为了告诉你：当问题规模增大时，我们需要学会利用历史信息，避免重复劳动。这种思想不仅适用于字符串匹配，也适用于我们日常的工程实践。

下一期预告：《两数相除》——位运算与边界处理的巅峰对决

附录：思考题

看完这篇文章，你可以试着回答：

欢迎在评论区留下你的思考！