从strstr实现到KMP算法：C语言字符串查找的深度解析与实践

1. 从一道面试题说起为什么我们要自己实现 strstr最近在带新人做代码练习发现一个挺有意思的现象很多朋友对标准库函数用得很熟比如strstr、strcpy但一旦被问到“如果让你自己实现一个你会怎么写”思路就容易卡壳。这不前两天就有人拿了一道题来问我“实现一个字符串查找的简单函数模拟strstr”。乍一看这题太基础了不就是在一个字符串里找另一个字符串嘛。但真动手写起来从边界条件处理到性能优化能踩的坑还真不少。strstr这个函数在 C 语言的标准库string.h里它的原型是char *strstr(const char *haystack, const char *needle)。简单说就是在“干草堆”haystack里找“针”needle找到了就返回第一次出现位置的指针找不到就返回NULL。听起来很简单对吧但自己实现它远不止是调用一个库函数那么简单。这背后涉及到字符串遍历、指针操作、边界判断甚至是一些简单的算法思想。能清晰、高效、无 bug 地实现它是检验一个程序员对 C 语言字符串和指针理解深度的绝佳试金石。所以今天我们就来彻底拆解一下这个“简单”的函数。我会从最朴素的暴力匹配法开始一步步带你写出代码然后我们会深入讨论那些容易出错的细节比如空指针、空字符串该怎么处理。接着我们会聊聊这种方法的效率问题并引入更高效的 KMP 算法思路作为对比和延伸。最后我还会分享几个在实际面试或工程中围绕字符串查找可能衍生出来的问题和优化技巧。无论你是正在准备技术面试还是想夯实 C 语言基础相信这篇内容都能给你带来实实在在的收获。2. 核心需求与函数接口设计在动手写代码之前我们必须先把需求理清楚。模拟strstr我们到底要模拟什么首先是函数的行为。给定两个字符串haystack主串和needle子串我们的函数要在haystack中查找第一次完整出现needle的位置。例如haystack hello world,needle world函数应该返回指向w的指针。如果needle是空字符串按照 C 标准库的约定应该返回haystack的起始地址。如果找不到则返回NULL。其次是函数的接口。为了和标准库保持一致我们的函数原型应该设计为char *my_strstr(const char *haystack, const char *needle);使用const修饰指针参数表明函数内部不会修改这两个字符串的内容这是一个良好的编程习惯也能增加函数的通用性。最后也是最重要但最容易被忽略的是异常或边界情况的处理。这是面试官考察的重点也是代码健壮性的体现。我们需要考虑指针为 NULL如果haystack或needle指针本身是NULL我们的函数该怎么办标准库的strstr在传入NULL时行为是未定义的通常会导致程序崩溃。但在我们自己实现时出于健壮性考虑可以也建议增加对NULL的检查并返回NULL或进行断言。空字符串如前所述needle为空串时应返回haystack。needle比haystack长显然不可能找到应尽早返回NULL。把这些需求明确下来我们才能写出逻辑严密的代码。很多初学者写的查找函数跑不过所有测试用例问题往往就出在这些边界条件没有考虑周全。3. 暴力匹配法最直观的实现与逐行解析理解了需求我们就可以开始实现最经典的解法——暴力匹配法Brute-Force也有人叫它朴素匹配法。它的思想非常直接从haystack的第一个字符开始尝试与needle的第一个字符匹配如果匹配成功就同时比较下一个字符直到needle的所有字符都匹配成功如果在某个位置匹配失败则将haystack的匹配起始点向后移动一位再重新开始新一轮的匹配。下面我们一步步实现并解析这个算法3.1 基础版本实现我们先写出一个最基础的版本暂时不处理边界条件聚焦于核心匹配逻辑。char *my_strstr_naive(const char *haystack, const char *needle) { // 参数检查暂时省略 const char *h haystack; // 用于遍历 haystack 的指针 const char *n needle; // 用于遍历 needle 的指针 const char *start haystack; // 记录每一轮匹配的起始位置 while (*start ! \0) { // 主循环遍历 haystack h start; // 每一轮都从新的 start 位置开始匹配 n needle; // 每一轮 needle 都从头开始 // 内层循环逐个字符比较 while (*n ! \0 *h ! \0 *h *n) { h; n; } // 判断内层循环结束的原因 if (*n \0) { // needle 的所有字符都匹配完了 return (char *)start; // 找到返回起始位置 } // 如果是因为 *h ! *n 或者 *h 先到头了而退出则匹配失败 start; // 将匹配起始点向后移动一位继续下一轮 } // 遍历完整个 haystack 都没找到 return NULL; }代码逻辑拆解三层指针我们使用了三个指针。start指针是“锚点”它标记了在haystack中当前尝试匹配的起始位置。h和n是“游标”分别从start和needle开头向后移动进行逐字符比较。外层循环while (*start ! \0)控制着匹配的起始点在整个haystack上滑动。内层循环while (*n ! \0 *h ! \0 *h *n)是核心比较过程。三个条件必须同时满足needle没到头、haystack没到头、当前字符相等。只要一个条件不满足循环就停止。匹配成功判断内层循环结束后检查*n是否为\0。如果是说明needle的每一个字符都成功匹配了此时返回start指针。匹配失败处理如果*n不是\0说明中途失败了。此时只需将start加一然后进入下一轮外层循环。这个版本已经实现了核心功能但它还不健壮。我们来给它加上之前讨论的边界处理。3.2 增强版本加入健壮性处理一个工业级别或面试官期待的版本必须妥善处理边界情况。#include assert.h // 为了使用 assert char *my_strstr(const char *haystack, const char *needle) { // 1. 防御性编程检查输入指针 if (haystack NULL || needle NULL) { // 处理方式1返回 NULL表示无效输入 // return NULL; // 处理方式2使用断言在调试阶段立即暴露问题更推荐 assert(haystack ! NULL needle ! NULL); // 如果断言被禁用仍可返回 NULL return NULL; } // 2. 处理 needle 为空字符串的特殊情况 if (*needle \0) { // C 标准规定查找空字符串应返回 haystack return (char *)haystack; } // 3. 核心匹配逻辑同基础版本但变量名稍作调整以清晰 const char *h; const char *n; const char *current_start haystack; while (*current_start ! \0) { h current_start; n needle; while (*n ! \0 *h ! \0 *h *n) { h; n; } if (*n \0) { // 找到匹配 return (char *)current_start; } // 提前结束优化如果剩余 haystack 长度已小于 needle 长度则不可能匹配 // 这里先不实现后续优化部分会讲 current_start; } // 4. 遍历完毕未找到 return NULL; }关键增强点解析NULL检查我使用了assert。assert在调试版本通常未定义NDEBUG宏中如果条件为假会终止程序并打印错误信息能快速定位问题。在发布版本中assert会被定义为空不影响性能。这是一种非常专业的做法。当然你也可以选择直接返回NULL但这样可能会把错误隐藏起来不利于调试。空串处理if (*needle \0)这个判断至关重要。它直接遵循了 C 语言标准库的规范。很多自己实现的字符串函数会忽略这一点导致行为与标准库不一致这是个大坑。指针类型转换返回值我们使用了(char *)进行强制转换。因为我们的参数是const char *但返回的指针可能需要用于修改尽管查找函数通常不修改为了匹配标准库的char *返回类型需要进行转换。注意返回haystack或current_start的const属性会被去掉调用者如果通过这个指针修改字符串对于字面量字符串会导致未定义行为但这与标准库strstr的行为一致。注意这里有一个非常重要的编程习惯。在内层循环的判断条件*h ! \0其实是多余的。因为如果*h是\0而*n不是\0那么*h *n这个条件必然为假\0不等于任何非结束符字符循环也会终止。所以可以简化为while (*n ! \0 *h *n)。但保留*h ! \0可以让逻辑更清晰对初学者更友好。在追求极致简洁的代码中常常会省略它。4. 算法效率分析暴力法的时间复杂度与最坏情况我们的暴力匹配法写出来了也能正确工作。但它的性能怎么样呢这是面试中紧接着就会问到的问題。我们来分析一下时间复杂度。设haystack的长度为nneedle的长度为m。最好情况needle就在haystack的开头或者很快就能匹配成功。这时时间复杂度是O(m)非常快。最坏情况这是我们要重点关注的。考虑这个例子haystack AAAAAAAAB(长度为 n)needle AAAB(长度为 m)。第一轮从haystack[0]开始匹配比较A-A,A-A,A-A直到A-B失败比较了m次。第二轮从haystack[1]开始又是比较A-A,A-A,A-A,A-B失败比较了m次。...几乎每一轮都要进行差不多m次比较直到needle的B终于对上haystack末尾的B。总共需要比较大约(n - m 1) * m次。当n远大于m时时间复杂度近似为O(n * m)。对于短字符串O(n*m)是可以接受的。但如果是在一个很长的文本例如一篇几万字的文章中查找一个较长的模式串这个效率就可能成为瓶颈。例如在基因组序列分析中字符串长度动辄以亿计暴力法就完全不可行了。那么有没有办法优化呢有的。这就是著名的KMP 算法。它能在O(n m)的时间内完成查找代价是需要一个O(m)的额外空间来存储一个“部分匹配表”。在面试中如果你能先写出暴力法再分析其效率最后提到 KMP 并简述其思想绝对是巨大的加分项。5. 优化策略提前失败与 KMP 算法思想简介虽然我们不一定需要在模拟strstr的简单函数里实现 KMP但了解优化思路和更高级的算法是很有必要的。这里我们讨论两种思路。5.1 优化一长度检查与提前失败这是一个简单而有效的优化。在开始繁琐的双重循环之前我们可以先进行长度判断。// 在核心循环开始前计算长度或者直接遍历一次 // 方法1使用 strlen (需要 #include string.h) size_t haystack_len strlen(haystack); size_t needle_len strlen(needle); if (needle_len haystack_len) { return NULL; // 子串比主串还长绝对找不到 } // 方法2如果不允许用 strlen可以在循环中融入这个判断 const char *h; const char *n; const char *current_start haystack; // 我们可以在外层循环条件中增加一个判断剩余长度是否足够 // 但为了清晰我们可以在循环内判断 while (*current_start ! \0) { // 手动检查从 current_start 开始的剩余长度是否 needle_len const char *temp_h current_start; const char *temp_n needle; int remaining_len 0; // 快速计算剩余长度或者与匹配过程合并 // 更优雅的方式是在循环开始时如果 current_start - haystack needle_len haystack_len则 break。 // 但因为我们没有预先计算 haystack_len所以这个优化在不用 strlen 时稍显繁琐。 }实际上在知道长度的情况下外层循环的次数可以缩减为n - m 1次而不是n次。这是一个微小的但确实存在的优化。在面试中即使你不实现说出这个想法也能体现你的思维全面性。5.2 优化二KMP 算法核心思想KMPKnuth-Morris-Pratt算法的精髓在于当某次匹配失败时needle串应该向右滑动多远而不是仅仅向后移动一位。它利用已经匹配成功的部分信息避免回溯haystack的指针i只移动needle的指针j。其核心是一个叫做部分匹配表Partial Match Table或前缀函数Prefix Function的数组next[]。对于needle中的每个位置jnext[j]表示needle[0...j-1]这个子串中最长的相等前缀和后缀的长度。举例说明needle ABABCj0: 子串“” 无前缀后缀长度为0。j1: 子串“A” 前缀后缀均为空长度为0。j2: 子串“AB” 前缀有“A”后缀有“B”不相等长度为0。j3: 子串“ABA” 前缀有“A”, “AB”后缀有“BA”, “A”。相等的只有“A”和“A”长度为1。j4: 子串“ABAB” 前缀有“A”,“AB”,“ABA”后缀有“BAB”,“AB”,“B”。相等的最长串是“AB”长度为2。当我们在haystack ABABABC中查找ABABC时匹配到haystack[4] A和needle[4] C失败。暴力法会将haystack指针回溯到[1]needle指针回溯到[0]。KMP 算法查表next[4]2。这意味着needle[0...1](“AB”) 已经和haystack[2...3]匹配成功了。所以我们可以直接将needle的指针j从4回退到2(j next[j])而haystack的指针i保持在4不动。然后比较haystack[4]和needle[2]。这样我们就避免了haystack指针i的回溯将时间复杂度降到了O(nm)。在面试中实现完整的 KMP 代码可能时间紧张但清晰地阐述其“利用已匹配信息避免主串指针回溯”的思想并说明next数组的含义和构建方法就足以证明你的算法功底了。6. 测试用例设计如何验证你的实现是正确的代码写完了怎么证明它是对的设计全面的测试用例是关键。一个好的测试集应该覆盖正常情况和所有边界情况。#include stdio.h #include string.h // 用于和标准库 strstr 对比 // 假设我们的 my_strstr 函数声明在这里 char *my_strstr(const char *haystack, const char *needle); void test(const char *haystack, const char *needle, const char *test_case) { char *result my_strstr(haystack, needle); char *expected strstr(haystack, needle); // 使用标准库作为参照 if ((result NULL expected NULL) || (result ! NULL expected ! NULL strcmp(result, expected) 0)) { printf([PASS] %s\n, test_case); } else { printf([FAIL] %s\n, test_case); printf( Haystack: \%s\\n, haystack); printf( Needle: \%s\\n, needle); printf( Expected: %s\n, expected ? expected : NULL); printf( Got: %s\n, result ? result : NULL); } } int main() { printf(Testing my_strstr...\n\n); // 1. 基础功能测试 test(hello world, world, 基础查找); test(hello world, hello, 查找在开头); test(hello world, ld, 查找在结尾); test(hello world, o w, 查找在中间); test(abababc, ababc, 包含部分匹配的复杂情况); // 2. 找不到的情况 test(hello world, xyz, 完全找不到); test(short, longer, 子串比主串长); test(abc, abcd, 子串比主串长且部分匹配); // 3. 空字符串和空指针测试 test(hello world, , 查找空字符串); test(, hello, 主串为空); test(, , 两者都为空); // test(NULL, hello, 主串为 NULL); // 取决于你的实现如果用了 assert运行时会中断 // test(hello, NULL, 子串为 NULL); // test(NULL, NULL, 两者都为 NULL); // 4. 重复字符与最坏情况测试测试性能 test(AAAAAAAAB, AAAB, 最坏情况测试); // 5. 重叠匹配测试 test(ababababc, ababc, 重叠模式匹配); printf(\nAll tests completed.\n); return 0; }测试用例设计思路基础功能验证正常能找到的情况包括在开头、中间、结尾。查找失败验证确实找不到的情况特别是子串更长的情况。边界条件空字符串、空指针需谨慎根据你的实现决定是否测试。这是最容易出错的地方。压力与特殊情况像AAAAAAAAB找AAAB这种可以测试算法在最坏情况下的正确性虽然不测性能。ababababc找ababc则涉及重叠模式的匹配。与标准库对比这是最可靠的验证方法。确保你的函数在尽可能多的情况下与strstr行为一致。自己跑一遍这些测试能帮你发现很多逻辑上的疏漏。养成写完代码立即设计测试用例的习惯是专业程序员的基本素养。7. 常见陷阱与经验分享最后结合我自己的经验分享几个在实现字符串查找函数时容易踩的坑和可以优化的点。陷阱一指针越界访问这是 C 语言字符串操作的老大难问题。在内层循环中while (*h ! \0 *n ! \0 *h *n)这个条件的顺序很重要。如果写成while (*h *n *h ! \0 *n ! \0)当h指向\0而n不是\0时会先判断*h *n即\0 x这没问题结果是false。但更安全、更常见的写法是把结束符判断放在前面或者像我们之前讨论的直接省略*h ! \0因为\0不可能等于一个非\0的字符。理解这一点能避免很多诡异的崩溃。陷阱二返回值类型转换我们的函数返回char *但内部指针是const char *。直接返回会报类型不兼容的警告。需要进行强制转换(char *)。但请务必清楚这去掉了const属性。调用者如果试图修改返回指针指向的常量字符串如字面量会导致运行时错误。这一点和标准库strstr的行为是一致的所以我们在模拟时也遵循此约定。经验一使用assert进行调试在函数开头对NULL指针使用assert是我强烈推荐的做法。它在调试阶段像一把利剑能瞬间定位到非法参数传入的位置而不是让错误在后续的指针解引用中随机爆发。在assert后面再返回一个安全值如NULL可以保证发布版本也有定义良好的行为。经验二考虑使用size_t记录长度在优化版本中我们提到了提前进行长度检查。strlen的返回类型是size_t这是一个无符号整数类型。在比较if (needle_len haystack_len)时使用无符号类型比较安全。如果使用int当字符串非常长时可能会发生溢出导致判断错误。经验三清晰命名胜过简短命名在最初的示例中我用了h,n,start。在更复杂的项目或团队协作中更推荐使用haystack_ptr,needle_ptr,current_haystack_pos这样的名字。虽然打字多了但代码的可读性和可维护性会大大提升别人或三个月后的你自己一眼就能看懂指针的用途。实现一个strstr看似简单但它像一面镜子能照出一个程序员对基础知识的掌握程度、思维的严谨性以及对代码质量的追求。希望这篇详细的拆解能帮你不仅写出一个能跑的函数更能理解其背后的每一个“为什么”。下次再遇到类似“模拟实现”的问题你就能从容应对了。