代码训练LeetCode(33)字符串首次匹配
代码训练(33)找出字符串中第一个匹配项的下标
Author: Once Day Date: 2025年6月13日
漫漫长路，才刚刚开始…
全系列文章可参考专栏: 十年代码训练_Once-Day的博客-CSDN博客
参考文章:
- 28. 找出字符串中第一个匹配项的下标 - 力扣（LeetCode）
- 力扣 (LeetCode) 全球极客挚爱的技术成长平台
文章目录
- 代码训练(33)找出字符串中第一个匹配项的下标
- 1. 原题
- 2. 分析
- 3. 代码实现
- 4. 总结
1. 原题
给你两个字符串
haystack和needle，请你在haystack字符串中找出needle字符串的第一个匹配项的下标（下标从 0 开始）。如果needle不是haystack的一部分，则返回-1。提示：
1 <= haystack.length, needle.length <= 104haystack和needle仅由小写英文字符组成
示例 1:
输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。
示例 2:
输入：haystack = "leetcode", needle = "leeto"
输出：-1
解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。
2. 分析
这个问题要求我们在一个字符串（haystack）中寻找另一个字符串（needle）的首次出现位置，并返回其索引。如果不存在，返回-1。这是一个经典的字符串搜索问题，常见于文本编辑器的查找功能中。
要解决这个问题，有几种方法：
- 暴力法：遍历haystack，对每一个起始位置，检查needle是否从该位置开始。
- KMP算法：一种更高效的字符串匹配算法，可以在不回溯haystack的情况下，通过预处理needle来实现快速匹配。
- Rabin-Karp算法：一种使用哈希技术的字符串搜索算法，适用于多模式搜索。
- Boyer-Moore算法：一种高效的单模式字符串搜索算法，利用坏字符规则和好后缀规则来跳过尽可能多的无效位置。
在这里，我们首先实现暴力方法，因为它易于理解和实现。接着，我们可以讨论KMP算法，它在实际应用中更为高效。
暴力法：
- 遍历haystack中每一个可能的起始位置。
- 比较haystack中从当前位置开始的子串是否与needle相匹配。
- 如果匹配，返回当前索引。
- 如果遍历完所有可能的起始位置都没有找到匹配，返回-1。
KMP算法：
- 预处理needle生成部分匹配表（也称为"pi"表或"prefix"表）。
- 使用该表来在不回溯haystack的情况下，有效地跳过needle中已知不匹配的部分。
性能优化关键点：
- 对于暴力法，性能瓶颈在于可能的冗余比较，特别是当needle较长且haystack较大时。
- KMP算法通过预处理needle，避免不必要的比较，极大地提高效率。
3. 代码实现
#include <stdio.h>
#include <string.h>int strStr(char *haystack, char *needle) {int hLen = strlen(haystack);int nLen = strlen(needle);if (nLen == 0) return 0;for (int i = 0; i <= hLen - nLen; i++) {int j;for (j = 0; j < nLen; j++) {if (haystack[i + j] != needle[j]) {break;}}if (j == nLen) return i;}return -1;
}int main() {char haystack[] = "sadbutsad";char needle[] = "sad";printf("Output: %d\n", strStr(haystack, needle));return 0;
}
代码解释：
strStr函数通过双层循环实现暴力匹配。- 外层循环遍历haystack中的每个起始位置。
- 内层循环检查needle是否在当前位置开始。
4. 总结
通过这个问题，我们可以学习和掌握字符串匹配的基本概念和方法。从简单的暴力法到更高级的KMP算法，我们可以看到算法优化如何显著提高程序的性能。对于初学者来说，理解不同算法的原理和实现是提升编程能力的重要步骤。