KMP比暴力匹配快因主串指针不回退，利用LPS数组跳过无效比较，时间复杂度从O(n×m)降至O(n+m)；computeLPS需注意len非下标、回退用lps[len-1]而非len--、边界判空防越界。
为什么 KMP 比暴力匹配快？
暴力匹配每次失配就回退主串指针，最坏 O(n×m)；KMP 利用已匹配子串的「前后缀重合信息」跳过无效比对，把主串指针保持前进，降到 O(n+m)。关键不在“多快”，而在“不回退”——这对流式处理、内存受限或长文本场景很实在。
computeLPS 函数怎么写才不出错？
LPS（Longest Proper Prefix which is also Suffix）数组是 KMP 的核心预处理，常见错误是边界条件写崩、循环变量混淆、或者把 len 和下标混用。
- 初始化
lps[0] = 0，因为单字符没有 proper prefix - 用
len记录当前最长匹配前缀长度，不是下标；i才是遍历模式串的下标 - 当
pattern[i] != pattern[len]且len > 0时，必须用len = lps[len-1]回退——不是len--，否则漏掉跳跃信息 - 别在
len == 0且仍不匹配时继续回退，会越界
简短示例：
void computeLPS(const string& pat, vector<int>& lps) {
lps[0] = 0;
int len = 0, i = 1;
while (i < pat.size()) {
if (pat[i] == pat[len]) {
len++;
lps[i] = len;
i++;
} else {
if (len != 0) len = lps[len-1]; // 关键：跳转，非递减
else {
lps[i] = 0;
i++;
}
}
}
}
KMP 搜索循环里最容易漏掉的边界检查
主搜索循环看似简单，但两个地方极易 crash 或漏匹配：
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
立即学习“C++免费学习笔记（深入）”；
-
j（模式串下标）为 0 时，lps[j-1]会越界——必须先判j > 0再取lps[j-1] - 匹配成功后，
j被设为lps[j-1]继续找重叠匹配，但如果j == 0就不该再取lps[-1] - 别忘了在
j == pat.size()时记录位置后，立刻执行j = lps[j-1]（如果j > 0），否则错过像"aaaa"在"aaaaaa"中的多次重叠匹配
典型错误写法：if (j == m) j = lps[j-1]; ——没判 j > 0 就直接访问 lps[j-1]。
C++ 实现要注意的性能和兼容性细节
STL 的 std::string 迭代器和索引访问都是 O(1)，没问题；但如果你用 char* + strlen，每次调用 strlen 是 O(m)，会把预处理拉回 O(m²)。
- 把
pat.size()和txt.size()提前存成const size_t m, n，避免循环中反复调用成员函数 -
lps数组用vector<int>即可，别用vector<size_t>——负值判断（如len > 0）会触发隐式转换警告甚至逻辑翻转 - 若模式串为空（
m == 0），直接返回 0 或按需处理，别让lps分配 0 元素后还去访问lps[0] - Windows 下用
std::string处理 UTF-8 文本没问题，但 KMP 本身只认字节——遇到多字节字符要先做编码切分，否则会切在中间导致错位
真正卡住人的往往不是算法逻辑，而是 lps 索引和 j 更新那几行的符号与边界组合。写完务必用 "ababab" 匹配 "abababc" 和 "aaaa" 匹配 "aaaaaa" 这两类边界样例过一遍。
