KMP的价值在于最坏时间复杂度严格为O(n+m)，适用于需确定性延迟的场景；computeLPS须设lps[0]=0并正确回退；主循环中j和i更新需避免死循环与漏匹配；实际项目通常无需手写，C++20 std::search更优；KMP不支持UTF-8，需转u32string或用ICU。
为什么不能直接用 std::string::find 就完事？
多数场景下，std::string::find 确实够用，它底层通常已做优化（如混合 BM / Sunday 启发式），平均性能不差。但 KMP 的价值不在“更快”，而在「最坏时间复杂度严格为 O(n + m)」——当你必须保证线性、且输入模式串（pattern）可能高度退化（比如全是 'a'）、文本串（text）也恶意构造时，朴素匹配会退化到 O(n×m)，而 KMP 不会。
典型触发场景：编译器词法分析预处理、网络包深度检测（DPI）、嵌入式资源受限环境需确定性响应延迟。
computeLPS 函数怎么写才不出错？
LPS（Longest Proper Prefix which is also Suffix）数组是 KMP 的核心预处理结果。常见错误是边界判断混乱、指针/索引混用、或忽略 lps[0] == 0 的强制约定。
- 起始必须设
lps[0] = 0，因为长度为 1 的子串没有 proper prefix - 主循环从
i = 1开始，用len表示当前已匹配的前缀长度（也是上一个位置的 lps 值） - 当
pattern[i] != pattern[len]且len > 0时，要回退：len = lps[len - 1]；不能写成len--或len = lps[len] - 匹配成功后，
lps[i] = ++len，注意是先自增再赋值
void computeLPS(const std::string& pattern, std::vector& lps) { lps[0] = 0; int len = 0; size_t i = 1; while (i < pattern.length()) { if (pattern[i] == pattern[len]) { lps[i] = ++len; ++i; } else { if (len != 0) { len = lps[len - 1]; // 关键：不是 len-- } else { lps[i] = 0; ++i; } } } }
主匹配循环里 j 和 i 的更新逻辑为何总出 bug？
变量命名混乱是高频坑：i 是 text 指针，j 是 pattern 指针。常见错误包括：
立即学习“C++免费学习笔记（深入）”；
- 匹配成功后只写
j++却忘了i++（导致死循环） - 失配时只改
j却没动i（正确做法是仅j = lps[j-1]，i不回退） - 找到一个匹配后未重置
j就继续找下一个（应设j = lps[j-1]而非归零，否则漏掉重叠匹配，如在"aaaa"中找"aa"应返回索引 0 和 1）
std::vectorkmpSearch(const std::string& text, const std::string& pattern) { if (pattern.empty()) return {}; std::vector lps(pattern.length()); computeLPS(pattern, lps); std::vectorzuojiankuohaophpcnsize_tyoujiankuohaophpcn result; size_t i = 0, j = 0; while (i zuojiankuohaophpcn text.length()) { if (pattern[j] == text[i]) { ++i; ++j; } if (j == pattern.length()) { result.push_back(i - j); j = lps[j - 1]; // 注意：这里不是 j = 0 } else if (i zuojiankuohaophpcn text.length() && pattern[j] != text[i]) { if (j != 0) j = lps[j - 1]; else ++i; } } return result;}
实际项目中要不要手写 KMP？
绝大多数 C++ 工程无需手写。C++20 引入了
std::search配合std::default_searcher（基于 Boyer-Moore），性能通常优于手写 KMP；若需 C++17 及更早版本，absl::string_view::find（来自 Abseil）或boost::algorithm::find_all更可靠。真正需要手写 KMP 的情况极少：比如你正在实现一个轻量级脚本引擎，不允许链接第三方库，又必须支持超长日志行中查找重复指令序列，且对 worst-case 延迟有硬性要求——这时才值得把上面两个函数抠出来，加上
constexpr支持和char8_t适配。最容易被忽略的一点：KMP 对 Unicode（UTF-8）字符串无效。它按字节操作，而 UTF-8 中一个字符占 1–4 字节。真要处理中文等，必须先转为
std::u32string或用 ICU 库做正规化。
