std::string::find因采用O(mn)朴素匹配，在模式串含大量重复前缀时性能骤降；KMP通过预处理next数组实现O(n)稳定匹配，其核心是双指针动态回退而非暴力重置。
为什么 std::string::find 不够用，非得手写 KMP？
因为 std::string::find 是朴素匹配（O(mn)），在大量重复前缀的场景下会退化——比如在长文本中搜 "aaaaa...ab" 这类模式串，每次失配都要回退，性能断崖式下跌。KMP 的核心价值不是“炫技”，是当你要做高频、低延迟的子串定位（如日志过滤、协议解析），且模式串固定、文本流持续到来时，预处理一次 next 数组能换来 O(n) 稳定匹配。
next 数组怎么算？别背公式，看指针怎么走
关键不是记住“最长真前缀等于真后缀”，而是理解两个指针：i 扫描模式串当前位置，j 记录当前已匹配的前缀长度（即 next[i] 的值）。初始化 j = 0，从 i = 1 开始遍历：
- 如果
pattern[i] == pattern[j]，说明能延续匹配，next[i] = ++j - 否则，
j回退到next[j-1]（不是直接归零！这是 KMP 避免重复比较的精髓） - 回退后若
j == 0且仍不等，next[i] = 0
常见错误：把 next[0] 设为 -1 或 1 ——标准实现里 next[0] 必须是 0；还有人用递归或额外空间存中间状态，纯属增加理解和调试成本。
KMP 匹配主循环里，j 什么时候清零？
匹配时用 i 遍历文本，j 指向模式串已匹配长度。只有当 j == pattern.size() 时才算找到，此时记录位置并执行 j = next[j-1] 继续找下一个（若需重叠匹配）；但绝不能在失配时无条件 j = 0 ——那又退回朴素算法了。正确做法是：
立即学习“C++免费学习笔记（深入）”；
- 失配时：
while (j > 0 && text[i] != pattern[j]) j = next[j-1]; - 匹配成功后推进：
if (text[i] == pattern[j]) j++; - 检查是否完工：
if (j == pattern.size()) { /* found at i - j + 1 */ }
漏掉 while 而只写一次 j = next[j-1]，就会在形如 "aabaaab" 中漏掉第二次匹配。
C++ 实现要注意的三个细节
一是字符串索引：C++ std::string 下标从 0 开始，next 数组长度必须和模式串一致（next.size() == pattern.size()），别用 pattern.length() + 1；二是类型安全：size_t 和 int 混用会导致隐式转换警告甚至逻辑错误（比如 j 是 int，但 next[j-1] 在 j==0 时变成 next[-1]）；三是边界判断：构建 next 时，内层 while 循环必须检查 j > 0，否则 j-- 后下溢成极大正数。
真正难的不是写对一次，是下次维护时还能快速看懂那个 while 为什么不能换成 if ——这恰恰说明 KMP 的回退逻辑必须亲手推演两遍，而不是抄个模板就完事。
