字符串匹配与 KMP

给定文本串 text（长度 n）和模式串 pattern（长度 m），字符串匹配要找到模式第一次或全部出现的位置。

朴素算法从文本的每个起点重新比较，最坏需要 O(nm)。例如文本和模式都包含大量连续的 a，每次接近匹配成功后才在末尾失败，会反复比较相同字符。

KMP（Knuth-Morris-Pratt）利用模式串自身的前后缀信息：失配时不回退文本指针，而是把模式移动到仍可能匹配的最长位置。预处理 O(m)，匹配 O(n)，总时间 O(n+m)。

前缀函数 / LPS 数组

本章使用 lps（longest proper prefix which is also suffix）定义：

lps[i] = pattern[0..i] 的最长相等真前缀与后缀的长度

“真前缀”不能等于整个字符串。例如模式 ababaca 的 lps 为：

pattern: a b a b a c a
index:   0 1 2 3 4 5 6
lps:     0 0 1 2 3 0 1

pattern[0..4] = "ababa" 的最长相等真前后缀是 "aba"，所以 lps[4] = 3。

不同资料还会使用以 -1 开始的 next 数组或 nextval。它们表达的是相同的失配跳转思想，但下标和长度定义不同，代码公式不能混用。面试时应先明确采用哪一种定义。

如何构造 lps

计算 lps[i] 时，设 j = lps[i-1]，表示当前候选前缀长度：

1. 若 pattern[i] == pattern[j]，候选可扩展，令 j++；
2. 若失配且 j > 0，令 j = lps[j-1]，尝试更短的、仍可能匹配的前后缀；
3. 若退到 j == 0 仍失配，则 lps[i] = 0。

#include <string_view>
#include <vector>

std::vector<std::size_t> build_lps(std::string_view pattern) {
    std::vector<std::size_t> lps(pattern.size(), 0);

    for (std::size_t i = 1; i < pattern.size(); ++i) {
        std::size_t j = lps[i - 1];

        while (j > 0 && pattern[i] != pattern[j]) {
            j = lps[j - 1];
        }
        if (pattern[i] == pattern[j]) {
            ++j;
        }
        lps[i] = j;
    }
    return lps;
}

虽然代码中有嵌套 while，构造仍是 O(m)：i 只向前走，j 的回退总量受之前增长总量限制，不会对每个位置重新扫描整个前缀。

KMP 匹配过程

设 j 表示模式串已经匹配的字符数。处理 text[i] 前，核心不变量是：

text[i-j .. i) == pattern[0 .. j)

若 text[i] != pattern[j]，已经匹配的 pattern[0..j) 中，只有它的某个“既是前缀又是后缀”的部分可能继续与当前文本后缀对齐。最长候选长度正是 lps[j-1]，因此只回退 j，不回退 i。

std::size_t kmp_find(std::string_view text, std::string_view pattern) {
    if (pattern.empty()) return 0; // 与 string_view::find 的常见语义一致

    const std::vector<std::size_t> lps = build_lps(pattern);
    std::size_t j = 0;

    for (std::size_t i = 0; i < text.size(); ++i) {
        while (j > 0 && text[i] != pattern[j]) {
            j = lps[j - 1];
        }
        if (text[i] == pattern[j]) {
            ++j;
        }
        if (j == pattern.size()) {
            return i + 1 - pattern.size();
        }
    }
    return std::string_view::npos;
}

KMP 的关键优势不是“比较次数永远最少”，而是文本指针只前进不后退，从而保证最坏 O(n+m)。

查找全部出现位置

匹配到一个完整模式后，不要把 j 直接清零。令 j = lps[j-1]，可以保留模式自身的重叠后缀，继续寻找重叠匹配：

std::vector<std::size_t> kmp_find_all(
    std::string_view text, std::string_view pattern) {
    std::vector<std::size_t> positions;
    if (pattern.empty()) return positions; // 业务中应先约定空模式语义

    const std::vector<std::size_t> lps = build_lps(pattern);
    std::size_t j = 0;

    for (std::size_t i = 0; i < text.size(); ++i) {
        while (j > 0 && text[i] != pattern[j]) {
            j = lps[j - 1];
        }
        if (text[i] == pattern[j]) {
            ++j;
        }
        if (j == pattern.size()) {
            positions.push_back(i + 1 - pattern.size());
            j = lps[j - 1];
        }
    }
    return positions;
}

例如 text = "aaaaa"、pattern = "aaa"，匹配起点是 0、1、2；若命中后把 j 清零，就会漏掉重叠结果。

前缀函数的其他应用

lps 不只用于子串查找，它刻画了字符串的所有 border（既是前缀又是后缀的子串）。

枚举所有 border

完整字符串最长 border 长度为 lps[n-1]；继续跳到 lps[length-1]，可得到所有更短 border：

for (std::size_t length = lps.back(); length > 0;
     length = lps[length - 1]) {
    // pattern.substr(0, length) 是一个 border
}

判断周期和重复子串

对长度 n 的非空字符串，令：

period = n - lps[n - 1]

若 n % period == 0 且 period < n，字符串可由长度为 period 的子串重复构成。例如 ababab 的 lps.back() = 4，候选周期为 6 - 4 = 2，且 6 % 2 == 0。

流式匹配

j 就是匹配器跨数据块需要保存的状态。网络数据分块到达时，不必拼接并重新扫描历史文本；保留模式、lps 和当前 j，即可从下一个数据块继续匹配。

复杂度

阶段	时间	额外空间
构造 lps	O(m)	O(m)
搜索文本	O(n)	O(1)，不计 lps
完整 KMP	O(n+m)	O(m)
输出全部匹配	O(n+m+k)	结果数组 O(k)

其中 k 是匹配结果数量。即使文本和模式高度重复，KMP 也不会退化为 O(nm)。

与其他方法的选择

需求	常见选择
普通业务代码中查找一次子串	优先 std::string::find，表达意图最清晰
要求确定的线性最坏复杂度	KMP
同一模式匹配流式文本	KMP，可跨数据块保存 j
多个模式同时匹配	Trie + Aho-Corasick 自动机
比较字符串哈希、快速判断多个子串	Rolling Hash，但要考虑碰撞
从后向前跳过较长片段的实际搜索	Boyer-Moore 系列

标准没有规定 std::string::find 必须使用 KMP。工程中不应仅因为知道 KMP 就替换标准接口；KMP 更重要的价值是提供最坏线性保证，并复用前缀函数解决周期和 border 问题。

常见错误

1. lps[i] 存的是长度，不是匹配前缀的最后一个下标；
2. 失配时写 j = lps[j] 可能不缩小状态甚至越界，长度定义下应写 j = lps[j-1]；
3. 回退 j 时不应回退文本下标 i，否则会重复比较；
4. 只用一次 if 回退不够，失配后可能需要沿失败链连续回退，应使用 while；
5. 查找全部结果时，完整匹配后应回退到 lps[j-1]，否则会漏掉重叠匹配；
6. 空模式的结果必须提前约定；本文单次查找返回 0，全部匹配接口返回空结果；
7. 不要把 lps 长度版本与 next[0] = -1 的下标版本混用；
8. std::string 按字节存储 UTF-8。精确查找一段 UTF-8 字节序列可以直接使用 KMP，但若算法要求按 Unicode 字符、大小写折叠或规范化匹配，应先完成相应解码和标准化。

关联笔记

• 数组、前缀和与区间
• 递归、显式栈与字符串解码
• 图搜索、回溯与并查集