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 <h3>主匹配循环里 <code>j</code> 和 <code>i</code> 的更新逻辑为何总出 bug？</h3>
<p>变量命名混乱是高频坑：<code>i</code> 是 text 指针，<code>j</code> 是 pattern 指针。常见错误包括：</p>
<ul>
<li>匹配成功后只写 <code>j++</code> 却忘了 <code>i++</code>（导致死循环）</li>
<li>失配时只改 <code>j</code> 却没动 <code>i</code>（正确做法是仅 <code>j = lps[j-1]</code>，<code>i</code> 不回退）</li>
<li>找到一个匹配后未重置 <code>j</code> 就继续找下一个（应设 <code>j = lps[j-1]</code> 而非归零，否则漏掉重叠匹配，如在 <code>"aaaa"</code> 中找 <code>"aa"</code> 应返回索引 0 和 1）</li>
</ul>
<pre class="brush:php;toolbar:false;">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 <p>}</p><div class="aritcle_card flexRow artxards">
<div class="artcardd flexRow">
<a class="aritcle_card_img" rel="nofollow" href="/xiazai/gongju/2823" title="C++14"><img
src="https://img.php.cn/upload/manual/001/431/639/6ac8b33c327c4749.png" alt="C++14" onerror="this.onerror='';this.src='/static/lhimages/moren/morentu.png'" ></a>
<div class="aritcle_card_info flexColumn">
<a rel="nofollow" href="/xiazai/gongju/2823" title="C++14" class="overflowclass">C++14</a>
<p class="overflowclass">C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。</p>
</div>
<a rel="nofollow" href="/xiazai/gongju/2823" title="C++14" class="aritcle_card_btn flexRow flexcenter"><b></b><span>下载</span>
</a>
</div>
</div></size_t>
实际项目中要不要手写 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 库做正规化。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
