Lesson 25: 实现 my_strstr — 暴力字符串匹配
练习任务
难度：易
实现自己的 my_strstr(haystack, needle) 函数——在字符串 haystack（干草堆）中查找子串 needle（针）第一次出现的位置，返回指向该位置的指针；若未找到返回 NULL。如果 needle 是空字符串，返回 haystack。这是标准库 <string.h> 中 strstr 的手写版本。
本课共有 4 组测试用例：
输入 "hello world" + "world" → 输出 "found: world"
输入 "hello world" + "xyz" → 输出 "not found"
输入 "aaaa" + "aa" → 输出 "found: aaaa"
输入 "hello" + "" → 输出 "found: hello" （空 needle）提示：暴力匹配的核心思路是「滑动窗口」——用一个宽度为
needle长度为m的窗口，在haystack上从左向右滑动。每到一个位置i，比较窗口内的m个字符是否与needle完全一致。外层循环变量i的取值范围是你需要思考的关键——i <= n - m中的等号为什么不能丢？
核心知识点
- C 字符串内存模型 —
'\0'（NUL 终止符）标记字符串结束，strlen返回不含'\0'的字符数 - 双重循环滑动窗口 — 外层
i控制窗口起点，内层j逐字符验证，两重循环各司其职 - 边界条件
i <= n - m— 等号确保窗口恰好在末尾时仍被检测，丢掉会遗漏匹配 const修饰符 —const char *haystack承诺函数不修改源字符串内容- 空串处理时
*needle == '\0'时返回haystack，与 C 标准strstr行为一致 - 指针返回值 — 找到时返回子串起始地址
&haystack[i]，未找到返回NULL - 最坏 O(n×m) 时间复杂度 — 每个位置都几乎比较完才失败时出现
- KMP 算法思想 —
next数组避免 j 回退，将复杂度降至 O(n+m)
代码框架
#include <stdio.h>
#include <string.h>
char *my_strstr(const char *haystack, const char *needle)
{
// 如果 needle 是空串，直接返回 haystack
// 在这里实现空串检查：if (*needle == '\0') ...
// 计算两个字符串的长度（用 strlen 函数）
// size_t n = strlen(haystack);
// size_t m = strlen(needle);
// 如果 haystack 比 needle 短，直接返回 NULL
// 在这里实现长度比较：if (n < m) ...
// 外层循环：i 从 0 到 n - m（等号不能丢！）
// 想一想为什么条件是 i <= n - m 而不是 i < n ?
// 当 needle 刚好在 haystack 末尾时会发生什么？
// 在这里实现外层循环：
// for (size_t i = 0; i <= n - m; i++) { ... }
// 内层循环：逐字符比较 haystack[i+j] 和 needle[j]
// 不匹配则立即 break 退出内层循环
// 在这里实现内层循环：
// for (j = 0; j < m; j++) {
// if (haystack[i + j] != needle[j]) break;
// }
// 如果内层循环完整跑完（j == m），说明全部匹配
// 返回匹配位置的指针：return (char *)(haystack + i);
// 循环结束仍未找到，返回 NULL
}
int main(void)
{
char haystack[256], needle[256];
// 用 fgets 从标准输入读取两行：第一行是 haystack，第二行是 needle
// 在这里读取输入：
// fgets(haystack, sizeof(haystack), stdin);
// fgets(needle, sizeof(needle), stdin);
// 去掉每行末尾的换行符 '\n'
// 提示：遍历字符串直到遇到 '\n'，将其替换为 '\0'
// 注意：空行（直接回车）读到的是 "\n"，去掉后变成空串
// 在这里去掉换行符：
// int i = 0;
// while (haystack[i] && haystack[i] != '\n') i++;
// haystack[i] = '\0';
// i = 0;
// while (needle[i] && needle[i] != '\n') i++;
// needle[i] = '\0';
// 调用 my_strstr，根据返回值打印结果
// 在这里完成调用和打印：
// char *result = my_strstr(haystack, needle);
// if (result)
// printf("found: %s\n", result);
// else
// printf("not found\n");
return 0;
}阅读骨架后，尝试自己填充 // 在这里... 标记的部分。核心挑战在于：外层循环的终止条件是 i <= n - m 还是 i < n？内层循环什么时候退出、什么时候表示"完全匹配"？
TIP
先不要往下翻看参考解答。尝试理解滑动窗口的双重循环结构——外层控制窗口位置，内层逐字符验证。写完代码后用示例手动追踪一轮，确认逻辑正确。
深度讲解
1. C 字符串的内存模型
1.1 NUL 终止符——C 字符串的灵魂
回顾 Lesson 09 中学到的 C 字符串：C 语言没有内置的字符串类型，用以 '\0' 结尾的字符数组来表示字符串。'\0'（ASCII 码 0，也称 NUL 终止符）是不可见但至关重要的一个字节。
char s[] = "hello";
// "hello" 在内存中的实际占用是 6 个字节，不是 5 个：
// ┌───┬───┬───┬───┬───┬───┐
// │ h │ e │ l │ l │ o │ \0│
// └───┴───┴───┴───┴───┴───┘
// 0 1 2 3 4 5 ← 索引
printf("%zu\n", strlen(s)); // 5——strlen 不算 '\0'
printf("%zu\n", sizeof(s)); // 6——sizeof 算上 '\0'C 字符串的核心约定：
┌──────────────────────────────────────────────────┐
│ │
│ strlen 从头数到 '\0'（不含），即字符个数 │
│ sizeof 返回数组总大小（含 '\0'），即字节数 │
│ printf("%s", s) 从首地址打印，遇 '\0' 停止 │
│ 越 '\0' 继续读 = 越界，行为未定义 │
│ │
│ "hello" 在内存中的六个字节: │
│ h e l l o \0 │
│ 0x68 0x65 0x6C 0x6C 0x6F 0x00 │
│ [0] [1] [2] [3] [4] [5] │
│ │
│ strlen("hello") = 5 │
│ sizeof("hello") = 6 │
│ │
└──────────────────────────────────────────────────┘1.2 字符串就是地址——指针视角
char *p = "hello"; // p 指向只读字符串 "hello" 的首字符
char *q = p; // q 也指向同一地址
printf("%s\n", p); // hello —— %s 从 p 所指向的地址开始输出
printf("%s\n", p + 2); // llo —— p+2 跳过两个字符
printf("%c\n", *p); // h —— 解引用得到首字符
printf("%c\n", p[1]); // e —— p[1] 等价于 *(p+1)strstr 返回正是指向 haystack 内部某个位置的指针——这是 C 字符串函数的标准设计：不拷贝数据，只返回位置。
my_strstr("hello world", "world") 的返回值：
↓ 返回指向这个 'w' 的指针
h e l l o w o r l d \0
0 1 2 3 4 5 6 7 8 9 10
↑
返回后打印 "%s" 从这个位置开始 → 输出 "world"2. 滑动窗口双重循环——算法核心
2.1 滑动窗口的直觉
想象你有一把"尺子"，长度恰好等于 needle 的长度 m。把这把尺子放在 haystack 的最左端，比对这个位置上的 m 个字符和 needle 是否完全一致。如果一致——找到；如果不一致——尺子向右移一格，再比对。
haystack = "hello world" (n=11), needle = "world" (m=5)
位置 i=0:
┌─────────────┐
│ h e l l o │ w o r l d → "hello" vs "world" → ✗
└─────────────┘
位置 i=1:
┌─────────────┐
h │ e l l o w │ o r l d → "ello " vs "world" → ✗
└─────────────┘
... 继续滑动 ...
位置 i=6:
┌─────────────┐
h e l l o │ w o r l d │ → "world" vs "world" → ✓ 匹配！
└─────────────┘
返回 &haystack[6] → 打印 "%s" 得 "world"2.2 双重循环的结构
暴力匹配的代码骨架是一个外-内双层循环：
外层循环 i：从 0 到 n-m（窗口的起始位置）
内层循环 j：从 0 到 m-1（窗口内逐字符比较）
若 haystack[i+j] != needle[j] → 不匹配，break
内层循环退出时：
若 j == m（完整走完，没有 break）→ 从位置 i 完全匹配！返回 &haystack[i]
若 j < m（中途 break）→ 继续外层下一个 i
外层循环结束 → 未找到，返回 NULL2.3 逐步跟踪——以 "hello world" 中找 "world" 为例
初始状态:
haystack = "hello world" (n=11)
needle = "world" (m=5)
合法窗口起点: 0..6 (n-m = 6)
═══════════════════════════════════════════════════════════════
外层 i=0 — 窗口起点 0
═══════════════════════════════════════════════════════════════
内层比较 haystack[0+j] vs needle[j]:
j=0: haystack[0]=h vs needle[0]=w → 'h' ≠ 'w' → break
窗口 "hello" 不匹配 ✗
═══════════════════════════════════════════════════════════════
外层 i=1 — 窗口起点 1
═══════════════════════════════════════════════════════════════
j=0: haystack[1]=e vs needle[0]=w → 'e' ≠ 'w' → break
窗口 "ello " 不匹配 ✗
═══════════════════════════════════════════════════════════════
外层 i=2 — 窗口起点 2
═══════════════════════════════════════════════════════════════
j=0: haystack[2]=l vs needle[0]=w → 'l' ≠ 'w' → break
窗口 "llo w" 不匹配 ✗
... i=3,4,5 同样首字符就不匹配 ...
═══════════════════════════════════════════════════════════════
外层 i=6 — 窗口起点 6（最后一个合法位置 n-m=6）
═══════════════════════════════════════════════════════════════
j=0: haystack[6]=w vs needle[0]=w → 'w' = 'w' ✓ 继续
j=1: haystack[7]=o vs needle[1]=o → 'o' = 'o' ✓ 继续
j=2: haystack[8]=r vs needle[2]=r → 'r' = 'r' ✓ 继续
j=3: haystack[9]=l vs needle[3]=l → 'l' = 'l' ✓ 继续
j=4: haystack[10]=d vs needle[4]=d → 'd' = 'd' ✓ j 走到 5
内层循环结束，j==5==m → 全部匹配！
返回 &haystack[6] → 指向 "world" 的起始地址 ✓2.4 索引映射关系图解
双重循环中索引 i 和 j 的含义：
i=6 (窗口起点)
↓
h e l l o w o r l d
0 1 2 3 4 5 6 7 8 9 10 ← haystack 索引
↑ haystack[i] = haystack[6] = 'w'
j=0: haystack[i+0] = haystack[6] = 'w' vs needle[0] = 'w'
j=1: haystack[i+1] = haystack[7] = 'o' vs needle[1] = 'o'
j=2: haystack[i+2] = haystack[8] = 'r' vs needle[2] = 'r'
j=3: haystack[i+3] = haystack[9] = 'l' vs needle[3] = 'l'
j=4: haystack[i+4] = haystack[10]= 'd' vs needle[4] = 'd'
关键：haystack[i+j] 同时受外层的 i 和内层的 j 影响
i 决定"站在哪里开始看"，j 决定"站在当前位置后看第几个字符"3. 边界条件：为什么是 i <= n - m 而不是 i < n？
3.1 窗口大小与有效起点的物理限制
这是本课最重要的一个细节——如同学走路不能踩到悬崖边上，滑动窗口也不能滑出字符串边界。
haystack = "hello" (n=5), needle = "world" (m=5)
用 i <= n-m: i 的取值范围 0..0（只有 1 个位置，因为等长）
位置 i=0: 窗口 "hello"，合法 ✓
用 i < n: i 的取值范围 0..4（共 5 个位置！）
位置 i=0: 窗口 "hello"，合法 ✓
位置 i=1: 窗口 "ello?" → 越界！✗
位置 i=2: 窗口 "llo??" → 越界！✗
位置 i=3: 窗口 "lo???" → 越界！✗
位置 i=4: 窗口 "o????" → 越界！✗i <= n - m 的等号保证：当窗口右边界恰好等于 n 时，窗口仍在字符串内部。
窗口右边界计算：i + m
当 i = n - m 时，右边界 = (n-m) + m = n
访问范围：haystack[i..i+m-1] = haystack[n-m..n-1] ← 全在字符串内 ✓3.2 丢掉等号的代价
// ❌ 错误写法：用 i < n - m（丢了等号）
for (size_t i = 0; i < n - m; i++) { ... }
// 后果：当 needle 刚好在 haystack 末尾时
// i = n - m 时窗口对应 haystack[n-m..n-1]，恰好匹配
// 但循环条件 i < n-m 在 i == n-m 时退出，永远不会检查这个位置！
//
// 例子：haystack="helloworld", needle="world"
// n=10, m=5, n-m=5
// i=0 窗口"hello", i=1 窗口"ellow", ... i=5 窗口"world" ← 但不会执行！// ✅ 正确写法：用 i <= n - m（保留等号）
for (size_t i = 0; i <= n - m; i++) { ... }
// i 的取值范围：0, 1, 2, ..., n-m
// 最后一个合法的窗口起点 n-m 也会被检查到 ✓3.3 全边界情形的系统分析
| 边界情形 | n-m 的值 | i 范围 | 行为 | 说明 |
|---|---|---|---|---|
needle 为空串 "" | — | — | 直接返回 haystack | 不进入循环，*needle=='\0' 提前处理 |
| n < m（haystack 比 needle 短） | 负数 | 无 | 返回 NULL | n-m 为负（size_t 下溢为巨大值），需提前判 n<m |
| n == m（等长） | 0 | i=0 | 只检查位置 0 | i<=0 恰好检查一次 |
| needle 出现在开头 | ≥0 | i=0 即命中 | 返回 &haystack[0] | 首次即匹配 |
| needle 出现在末尾 | ≥0 | i=n-m 命中 | 返回 &haystack[n-m] | <= 的等号保证了末尾 |
WARNING
n < m 时 n - m 在无符号算术（size_t）下会发生下溢——0 - 5 得到的是 SIZE_MAX - 4（约 2^64 - 4），导致外层循环范围异常。务必在循环前添加 if (n < m) return NULL; 检查，否则程序行为不可预测。
// 演示无符号下溢的危险
#include <stdio.h>
#include <stddef.h>
int main(void)
{
size_t n = 5, m = 10;
size_t diff = n - m; // 不是 -5！而是 SIZE_MAX - 4
printf("n - m = %zu\n", diff);
// 输出: n - m = 18446744073709551611（64 位系统）
// 因此:
// for (i = 0; i <= SIZE_MAX-4; i++) ← 循环天文数字次！→ 超时/越界
return 0;
}4. 时间复杂度分析
4.1 最好、最坏、平均
| 情况 | 时间复杂度 | 场景描述 |
|---|---|---|
| 最好 | O(n) | 每个位置的首字符就不匹配，外层走 n-m+1 次，每次内层只比较 1 次 |
| 最坏 | O(n×m) | 每个位置都几乎比较完 m 个字符才失败 |
| 平均 | O(n×m/k) | k 与字符集大小和模式串结构有关 |
4.2 最坏场景：几乎匹配的陷阱
haystack = "AAAAAB" (n=6)
needle = "AAAAB" (m=5)
i=0: AAAAA? — j=0✓ j=1✓ j=2✓ j=3✓ j=4: A≠B → break (5 次比较)
i=1: AAAAB — j=0✓ j=1✓ j=2✓ j=3: A≠B → break (4 次比较)
总比较次数 = 5+4 = 9 ≈ (n-m+1)×m/2
当 haystack 全为 'A' 而 needle 为 "AA...AB" 时:
比较次数 ≈ Σ(i=0..n-m) { min(m, 最后一个不同位置) }
≈ O(n×m)这就是为什么在文本搜索（如浏览器 Ctrl+F）和DNA 序列匹配（4 种碱基，重复频繁）中，暴力匹配会慢得不可接受——需要更聪明的算法。这也是 KMP 等算法出现的动机。
5. 字符串匹配进阶：KMP 算法思想简介
5.1 暴力匹配的浪费在哪里？
回顾上一个"几乎匹配"的例子：当 i=0 的窗口比较到最后一个字符才失败时，我们已经读取了 "AAAA" 这 4 个匹配字符的信息——但暴力匹配在内层 break 后立刻丢弃所有信息，下一轮 i=1 回到窗口开头重新比对。
haystack = "AAAAAB", needle = "AAAAB"
i=0 窗口: A A A A B
✓ ✓ ✓ ✓ ✗ → 读了 5 个字符，知道前 4 个是 "AAAA"
但这些信息在下一次 i=1 时完全被丢弃了！
i=1 窗口: A A A A B
✓ ✓ ✓ ✗ → 又重新比对了 "AAA"...KMP 的核心洞察：既然我们已经知道 haystack[0..3] = "AAAA" 且 needle[0..3] = "AAAA"，那 needle 的前缀已经和 haystack 的一段后缀匹配上了——我们可以直接跳过已经确认匹配的部分，不把 i 回退，只调整 j 的位置。
5.2 next 数组的直觉——"失败后该从哪继续？"
KMP 算法预处理 needle，计算一个 next[j] 数组，含义是：当 needle[j] 匹配失败时，下一次应该用 needle 的哪个位置继续比较。
needle = "ABAAB"
索引: 0 1 2 3 4
字符: A B A A B
next 数组（一种常见定义）：
next[0] = -1 // 第一个字符就失败，移动 haystack
next[1] = 0 // B 失败，前缀 A 没有相等的真后缀，回到 0
next[2] = 0 // A 失败，前缀 AB 没有相等的真后缀
next[3] = 1 // A 失败，前缀 ABA 的相等真前缀/真后缀是 "A"（长度 1）
next[4] = 1 // B 失败，前缀 ABAA 的相等最长真前缀/真后缀是 "A"（长度 1）next 的核心是寻找 needle 的前缀中的最长相等真前缀和真后缀。这个概念的名字叫"前缀函数"（prefix function，π 数组）。
needle = "ABAAB"
前缀 "A": 无真后缀 → next[1] = 0
前缀 "AB": 真前缀 A, B；真后缀 B, A → 无相等 → next[2] = 0
前缀 "ABA": 真前缀 A, AB；真后缀 A, BA → "A" = "A" → next[3] = 1
前缀 "ABAA": 真前缀 A,AB,ABA；真后缀 A,AA,BAA → "A" = "A" → next[4] = 1（next 数组有若干种编号约定，不同教材 +1/-1 可能不同，但思想一致。）
5.3 KMP 的核心：只前进，不后退
暴力匹配 vs KMP：
暴力匹配:
i: 0 → 1 → 2 → 3 → ...（i 可能回退-1 + 步进）
j: 0 → 1 → 2 → 3 → 匹配失败 → 回退到 0 → 1 → 2 → ...
问题：i 和 j 来回移动，做了大量无效比较
KMP:
i: 0 → 1 → 2 → 3 → 4 → ...（i 只在匹配成功时前进！）
j: 0 → 1 → 2 → 失败！→ next[j] 箭头 → 继续比较（不回退到 0）
关键：i 从不后退，j 通过 next 数组跳到"可能继续匹配"的位置用 KMP 处理 "AAAAAAB" 找 "AAAAB"：
i=0 j=0 A=A ✓ → j=1
i=1 j=1 A=A ✓ → j=2
i=2 j=2 A=A ✓ → j=3
i=3 j=3 A=A ✓ → j=4
i=4 j=4 B=A ✗ → j = next[4] = 3（跳回 3，不回退 i）
i=4 j=3 A=A ✓ → j=4
i=5 j=4 B=B ✓ → j=5 → j==m，匹配！
比较次数：暴力 ≈ 25 次，KMP ≈ 10 次TIP
KMP 在本单元中没有对应练习，但它的思想——预处理模式串以利用失败信息——是字符串算法设计中的经典范式。理解了 next 数组（前缀函数），你可以进一步学习 Boyer-Moore（从右端开始比较，跳得更远）和 Aho-Corasick（同时匹配多个模式串，KMP 扩展到 trie 上）等高级匹配算法。
KMP 时间复杂度为 O(n+m)：预处理 needle 的 next 数组 O(m)，扫描 haystack O(n)。这是线性时间字符串匹配的基准。
6. 指针返回值与函数契约
6.1 返回指针 vs 返回下标
// 方式 A: 返回下标（-1 表示未找到）
int strstr_index(const char *haystack, const char *needle);
// 调用方还需再做一次数组访问: haystack[index]
// 且 -1 作为"未找到"的标记不够类型安全
// 方式 B: 返回指针（NULL 表示未找到）← C 标准库选择
char *strstr(const char *haystack, const char *needle);
// 调用方直接得到指向子串的指针，可以直接传给 printf 等函数返回指针的好处：
- 调用方无需再关心原始 buffer——拿到指针直接就是子串的起点
NULL是 C 语言中"无"的通用表达，语义清晰- 支持链式使用：
printf("%s", my_strstr(s, "key"));
6.2 const 修饰符——只读承诺
// strstr 的标准签名:
char *strstr(const char *haystack, const char *needle);
// ↑ const ↑ const
// haystack 和 needle 都是"只读输入"
// const 告诉调用者：
// 1. 我不会修改你传给我的字符串内容
// 2. 编译器会帮我检查——如果你在函数体内写了 *haystack='X'，编译报错const 是 API 设计中的"自文档"——只看函数签名就知道哪些参数是输入、哪些是输出。对于 strstr，两个参数都修饰为 const，返回值是 char*（指向 haystack 内部，拥有者仍是调用方）。
参考解答
练习: my_strstr 完整实现
#include <stdio.h>
#include <string.h>
char *my_strstr(const char *haystack, const char *needle)
{
/* 空串：C 标准规定返回 haystack */
if (*needle == '\0')
return (char *)haystack;
size_t n = strlen(haystack);
size_t m = strlen(needle);
/* haystack 比 needle 短，不可能匹配；同时防止 n-m 无符号下溢 */
if (n < m)
return NULL;
/* 外层循环：i 从 0 到 n-m（等号保证窗口末尾不会被遗漏） */
for (size_t i = 0; i <= n - m; i++) {
size_t j;
/* 内层循环：逐字符比较窗口与 needle */
for (j = 0; j < m; j++) {
if (haystack[i + j] != needle[j])
break; /* 不匹配，退出内层 */
}
/* 内层完整跑完 = 全部匹配 */
if (j == m)
return (char *)(haystack + i);
}
return NULL; /* 未找到 */
}
int main(void)
{
char haystack[256], needle[256];
fgets(haystack, sizeof(haystack), stdin);
fgets(needle, sizeof(needle), stdin);
/* 去掉 haystack 末尾的 '\n' */
int i = 0;
while (haystack[i] && haystack[i] != '\n')
i++;
haystack[i] = '\0';
/* 去掉 needle 末尾的 '\n'（空行变成空串 ✅） */
i = 0;
while (needle[i] && needle[i] != '\n')
i++;
needle[i] = '\0';
char *result = my_strstr(haystack, needle);
if (result)
printf("found: %s\n", result);
else
printf("not found\n");
return 0;
}核心逻辑解析：
- 空串提前返回：
*needle == '\0'检查避免了后续strlen("") = 0导致的n-m无符号运算问题。 - 长度保护：
if (n < m)既排除了明显无匹配的场景，也防止了n-m在size_t下的回绕（underflow）。 - 外层
i <= n-m：等号不能丢。当needle正好在haystack末尾时，i = n-m是唯一需要检查的起点。 - 内层
j == m判成功：如果内层break了，j会小于m；如果完整跑完，j恰好等于m（循环终止条件j < m失效）。
对照检查：外层循环条件写了
<=吗？内层比较用haystack[i+j]了吗？空 needle 返回haystack了吗？n < m提前判了吗？
课堂讨论
- 外层循环条件写成
for (i = 0; i <= n - m; i++)中的<=可以改成<吗？什么情况下结果会错？举例说明。 - 如果
needle是空字符串""，标准库strstr会返回什么？为什么这么设计？ - 暴力匹配最坏情况下为什么达到了 O(n×m)？设计一个具体的 haystack 和 needle 让暴力匹配的比较次数最大化。
- 这个算法是大小写敏感的吗？如果要实现大小写不敏感的匹配，需要在哪里做修改？
- KMP 算法中
next数组的物理含义是什么？为什么它可以避免 j 回退到 0？
讨论答案
Q1: i <= n-m 中的 <= 可以改成 < 吗？
不可以。丢掉等号会在 needle 恰好出现在 haystack 末尾时漏检。
具体例子：haystack = "hello world", needle = "world"。n=11, m=5, n-m=6。窗口的合法起点是 i=0 到 i=6。如果用 i < 6（即 i < n-m），i 只取 0,1,2,3,4,5——永远不会检查 i=6（窗口 "world" 的位置）。结果明明存在匹配却返回了 NULL。
这是一个典型的一刀切错误（off-by-one bug）：用 < 替代 <= 导致少检查一个位置。在循环边界设计时，画出字符串末尾的具体索引并验证"最后一个合法窗口的起点"的值是必要的好习惯。
Q2: 空字符串 needle 应该返回什么？
C 标准（man strstr）规定：如果 needle 是空串，返回 haystack。
理由是数学上的"空串约定"——空串被认为在任何字符串的任何位置都能匹配。这一定义使得很多字符串算法的边界条件更简洁（如 KMP 的 next[0] 通常设 -1）。
在实现中，这对应 if (*needle == '\0') return (char *)haystack; 的检查。如果不做这个检查，strlen(needle) 返回 0，后续 n-m 虽然等于 n，但无符号下溢风险在 n=0 时仍可能出现。
Q3: 设计一个最坏 O(n×m) 的场景
haystack = "AAAAAA" (n=6), needle = "AAAAB" (m=5)
这个场景的杀伤力在于：每次窗口几乎比到最后才失败——前 m-1 个字符都匹配，最后一个才不匹配。
i=0: AAAAA? → j=0✓ j=1✓ j=2✓ j=3✓ j=4✗ (5 次比较)
i=1: AAAAB? → j=0✓ j=1✓ j=2✓ j=3✗ (4 次比较)
总 = 5+4 = 9
推广：haystack 全为相同字符，needle 仅在最后一个位置不同
比较次数 ≈ (n-m+1) × (m+1) / 2 ≈ O(n×m)
这在真实场景中常见：
- DNA 序列中的 GC 重复区
- 日志文件中的重复时间戳
- 二进制文件中的 0x00 填充区Q4: 如何实现大小写不敏感匹配？
在内层比较时用 tolower() 转换后再比较。
#include <ctype.h>
// 修改内层比较:
for (j = 0; j < m; j++) {
if (tolower((unsigned char)haystack[i+j])
!= tolower((unsigned char)needle[j]))
break;
}要点：
tolower需要<ctype.h>，参数必须是unsigned char以避免负数传参的 UB- 大小写不敏感匹配比敏感匹配略慢（多两次函数调用/字符），但在文本搜索中更常用
- 这实际上就是标准库
strcasestr（GNU 扩展）的核心逻辑
Q5: KMP 的 next 数组的物理含义
next[j] 表示：当 needle[j] 匹配失败时，模式串 needle 内部哪些前缀已经与当前 haystack 的后缀匹配上了——下一次从 needle[next[j]] 开始比较即可。
具体来说：next[j] = needle[0..j-1] 这个子串的最长相等真前缀和真后缀的长度。
// needle = "ABABC"
// 索引 = 0 1 2 3 4
// 当 j=4 ('C') 失败时:
// 已匹配的 "ABAB" 的最长相等真前缀/真后缀是 "AB"（长度 2）
// 这意味着下一轮可以从 needle[2] 开始比较
// next[4] = 2这种设计的核心优势是j 只跳转不归零，i 只前进不后退——每个字符被读一次、最多比较两次，总的线性复杂度 O(n+m) 就从这里来。
课后练习
简单优化：首字符快速跳过。在内层比较开始前，先检查
haystack[i]和needle[0]是否相等——如果不相等，直接跳过内层循环。这个优化在什么场景下效果最好？知识点提示：观察"首字符不匹配"时原始算法也需要进入内层循环才 break，增加了 1 次无意义比较。首字符预检可以省下这次开销。
参考解答
cfor (size_t i = 0; i <= n - m; i++) { /* 首字符预检——跳过明显不匹配的位置 */ if (haystack[i] != needle[0]) continue; size_t j; for (j = 1; j < m; j++) { /* 从 j=1 开始！首字符已比较过 */ if (haystack[i + j] != needle[j]) break; } if (j == m) return (char *)(haystack + i); }效果最好的场景：字符集大（如 ASCII 通用文本），
needle的组成字符在haystack中不频繁出现。此时大量位置会被首字符预检直接跳过，比较次数近似 O(n)。效果最差的场景：
haystack全由needle[0]重复组成（如 DNA 序列 "AAAAA..."），首字符预检几乎全部"通过"，与原始暴力匹配无异。扩展：统计匹配次数。修改算法，不仅查找第一次出现，还要统计
needle在haystack中出现的总次数——允许重叠匹配（即haystack="aaaa", needle="aa"应返回 3 次：位置 0、1、2）。知识点提示：找到一次后不立即返回，而是继续扫描下一个位置。注意 i 只能递增 1，不能跳跃——重叠匹配要求窗口每次只移动一格。
参考解答
cint count_matches(const char *haystack, const char *needle) { if (*needle == '\0') return 0; /* 空串：按约定返回 0（有些教材按数学定义返回 strlen+1） */ size_t n = strlen(haystack), m = strlen(needle); if (n < m) return 0; int count = 0; for (size_t i = 0; i <= n - m; i++) { size_t j; for (j = 0; j < m; j++) { if (haystack[i + j] != needle[j]) break; } if (j == m) count++; /* 注意：无论是否匹配，i 都递增 1（允许重叠） */ } return count; }核心区别：找到匹配后 不 return 也不跳 i+=m（那会禁止重叠），而是正常让外层循环
i++进入下一个窗口起点。性能实验：比较暴力匹配在不同数据规模下的耗时。生成
haystack = "AAA...AB"（n=100~10000）、needle = "AA...AB"（m=10），分别测量暴力匹配的执行时间，记录 O(n×m) 的实际增长趋势。知识点提示：用
clock()函数测量时间。观察 m 固定时，运行时间和 n 是否大致成正比（线性×常数 = O(n×m) 中 m 为常数时近似 O(n)），以及 m 和 n 同比例增长时时间是否近似 O(n²)。参考解答
c#include <stdio.h> #include <string.h> #include <time.h> #include <stdlib.h> int main(void) { for (int n = 100; n <= 10000; n += 500) { /* 构造 haystack: n-1 个 'A' + 1 个 'B' */ char *haystack = malloc(n + 1); memset(haystack, 'A', n - 1); haystack[n - 1] = 'B'; haystack[n] = '\0'; /* 构造 needle: 9 个 'A' + 1 个 'B' */ char *needle = malloc(11); memset(needle, 'A', 9); needle[9] = 'B'; needle[10] = '\0'; clock_t start = clock(); volatile char *r = my_strstr(haystack, needle); clock_t end = clock(); double elapsed = (double)(end - start) / CLOCKS_PER_SEC; printf("n=%5d time=%.6f s result=%s\n", n, elapsed, r ? "found" : "miss"); free(haystack); free(needle); } return 0; }预期观察：m=10 固定，n 增长时，时间应大致线性增长（常数 m 使 O(n×m) ≈ O(n)）。如果同时增长 m，时间将呈二次增长。
阅读 material：man strstr 与 GNU C 库实现。用
man strstr查看官方文档，了解标准库的行为契约。对比你的实现和 glibc 的strstr源码（可在线搜索），看看工业级实现用了什么算法优化（如两路算法 Two-Way Algorithm、SIMD 向量化比较）。知识点提示：glibc 的
strstr实际上使用"两路算法"（Two-Way String Matching），兼顾 O(n) 时间复杂度和 O(1) 空间复杂度。你可以思考：为什么工业级实现选择两路算法而不是 KMP 或 BM？理论延伸：Boyer-Moore 坏字符规则。Boyer-Moore 算法从模式串的右端开始比较（而非左端）。阅读资料简要理解其"坏字符启发式"——当发生不匹配时，根据"坏字符"在模式串中的最近出现位置决定跳跃距离。描述它与 KMP "只前进不后退"思想的相似与不同。
知识点提示：KMP 利用"已匹配前缀"的信息决定 j 的跳转；Boyer-Moore 利用"坏字符"或"好后缀"的信息决定 i 的跳跃。BM 在实际中通常比 KMP 更快（尤其是大字母表场景），但最坏仍是 O(n×m)。
参考资料
man strstr— Linux 手册页，查看标准库strstr的函数签名与行为契约- 《算法导论》第 32 章 "字符串匹配" — 暴力匹配、Rabin-Karp、有限自动机、KMP 的严格算法描述
- glibc strstr 源码 — 工业级 C 标准库实现，使用 Two-Way Algorithm
- KMP Algorithm — GeeksforGeeks — KMP 的逐步图文讲解
- K&R《C 程序设计语言》§5.5 字符指针与函数 —
strlen、strstr等字符串函数的指针实现范式
"If debugging is the process of removing software bugs, then programming must be the process of putting them in." — Edsger W. Dijkstra