C++实现KMP算法查找子串索引详解

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 指针。常见错误包括：

• 匹配成功后只写 j++ 却忘了 i++（导致死循环）
• 失配时只改 j 却没动 i（正确做法是仅 j = lps[j-1]，i 不回退）
• 找到一个匹配后未重置 j 就继续找下一个（应设 j = lps[j-1] 而非归零，否则漏掉重叠匹配，如在 "aaaa" 中找 "aa" 应返回索引 0 和 1）

std::vector kmpSearch(const std::string& text, const std::string& pattern) {
    if (pattern.empty()) return {};
    std::vector lps(pattern.length());
    computeLPS(pattern, lps);
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 库做正规化。