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<int>& 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::vector<size_t> kmpSearch(const std::string& text, const std::string& pattern) {
if (pattern.empty()) return {};
std::vector<int> lps(pattern.length());
computeLPS(pattern, lps);
<pre class='brush:php;toolbar:false;'>std::vector<size_t> result;
size_t i = 0, j = 0;
while (i < 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 < 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 库做正规化。
