c++oding="utf-8" ?>
直接手写KMP易错在next数组构建：需严格满足“真前缀=真后缀”，常见错误是暴力比对或忽略j=next[j-1]回退；正确做法是复用已知信息，i从1开始、j初值为0，不匹配时while循环回退，匹配后next[i]=j+1且j++。
为什么直接手写 kmp_search 容易错在 next 数组构建逻辑？
多数人卡在 next 数组（也叫 lps，longest proper prefix which is also suffix）的递推上：不是简单统计前缀长度，而是要求「真前缀」且「等于真后缀」。常见错误是用双重循环暴力比对，或忽略 j = next[j-1] 的回退条件，导致匹配时跳过合法位置。
正确思路是边构建边复用已知信息：当 pattern[i] != pattern[j] 时，不重置 j=0，而是查 next[j-1] 找更短的可匹配前缀——这正是 KMP 摊还 O(n) 的关键。
实操建议：
-
next[0]必须初始化为 0（单字符无真前缀） - 主循环从
i = 1开始，j初始为 0，代表当前最长匹配前缀长度 - 遇到不匹配时，用
while (j > 0 && pattern[i] != pattern[j]) j = next[j-1];回退，不能只写if - 匹配成功后
next[i] = j + 1，然后j++
匹配过程里 i 和 j 的移动规则怎么不漏掉重叠匹配？
KMP 的核心优势是主串指针 i 不回溯。一旦 text[i] == pattern[j]，就同步推进；不等时，仅靠 next 调整 j，i 始终自增。这避免了暴力法中反复扫描同一段主串。
容易被忽略的边界：当 j 回退到 0 后仍不匹配，必须让 i 继续走，否则死循环。另外，找到一次匹配后，若需找所有位置，应设 j = next[j-1]（而非归零），才能检测到模式自身重叠的情况（如 "aaaa" 在 "aaaaaa" 中出现 3 次）。
实操要点：
- 匹配循环中，
i每轮必增：i++放在循环末尾或条件分支外 - 仅当
j == pattern.length()时记录位置，随后执行j = next[j-1]继续搜 - 若只需首次匹配，可在此处
return i - j
C++ 实现时 std::string 下标访问和 size_type 有什么坑？
std::string::size() 返回 size_type（通常是 unsigned long），直接与负数比较会触发隐式转换，导致无限循环。例如 while (j >= 0) 在 j 是无符号类型时恒为真。
更隐蔽的问题是 substr 或 at 越界抛异常，而 [] 不检查——调试时看似正常，上线后访问 pattern[j-1] 当 j==0 就越界。
安全做法：
- 把
j声明为int，避免无符号比较陷阱 - 所有数组访问前加
if (j > 0)再用next[j-1] - 构建
next数组时，用vector而非vector
示例片段：
vector<int> compute_next(const string& p) {
vector<int> next(p.size(), 0);
int j = 0;
for (int i = 1; i 0 && p[i] != p[j]) j = next[j-1];
if (p[i] == p[j]) ++j;
next[i] = j;
}
return next;
}
</int></int>
什么时候该用 std::search 而不是手写 KMP？
除非你在写算法题、教学代码，或明确需要获取所有重叠匹配位置，否则别手写。C++17 起 std::search 在 libstdc++ 和 libc++ 中已对短模式用 Boyer-Moore，长模式回退到类似 KMP 的线性算法，且经过充分测试和优化。
手写的典型劣势：边界处理 bug、未考虑 SSO（small string optimization）影响、缺乏 SIMD 加速。而 std::search 只需两行：
auto it = search(text.begin(), text.end(), pattern.begin(), pattern.end()); if (it != text.end()) return it - text.begin();
真正需要手写 KMP 的场景极少：比如嵌入式环境无 STL、定制化失败函数（如支持通配符）、或教学验证时间复杂度。生产代码里，过早优化字符串匹配反而增加维护成本。
最常被忽略的一点：KMP 的常数因子其实比暴力法大，短模式（pattern.length() ）下暴力往往更快。别为了“理论最优”放弃实测。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
