KMP 算法：从前缀函数到线性字符串匹配

字符串匹配要解决的问题是：给定文本串 text 和模式串 pattern，找出模式串在文本中出现的所有起点。例如在 ababa 中搜索 aba，答案是下标 0 和 2，两次出现可以重叠。

暴力算法在失配后把模式串整体右移一格，再从模式串开头比较。这会忘掉刚刚已经匹配成功的内容。KMP（Knuth–Morris–Pratt）算法的核心是：失配时不回退文本指针，而是利用模式串自己的前后缀结构，决定模式串应该退到哪里。

暴力匹配浪费在哪里

假设模式串是 ababac。若前五个字符 ababa 已经匹配，而下一位 c 失配，暴力算法会把模式串挪一格并从头比较。但已匹配串 ababa 的后缀 aba 恰好等于模式串前缀 aba，这三次比较其实不必重做。

已匹配ababac前五位成功，第六位失配

相等部分ababa前缀 aba 等于已匹配部分的后缀 aba

继续比较ababac保留长度 3，从 pattern[3] 继续，不移动文本指针

前缀函数 pi 的定义

对模式串 p，定义 pi[i] 为子串 p[0...i] 中，最长的相等真前缀与真后缀的长度。

• 前缀：必须从下标 0 开始；
• 后缀：必须在下标 i 结束；
• 真前缀、真后缀：不能等于整个 p[0...i]。

模式串 ababaca 的前缀函数如下：

下标 i0123456从 0 开始编号

字符ababacac 会破坏此前长度 3 的候选边界

pi[i]0012301完整数组为 [0, 0, 1, 2, 3, 0, 1]

例如 p[0...4] = ababa，最长相等真前后缀都是 aba，所以 pi[4] = 3。而 ababac 没有非空的相等前后缀，所以 pi[5] = 0。

如何在线性时间构造 pi

从左到右计算 pi[i]。在处理 i 时，先令 j = pi[i - 1]，这表示前一个子串的最长边界长度。接下来尝试用 p[i] 把这条边界向右延长：

• 若 p[i] == p[j]，边界成功增长一位，令 ++j；
• 若不相等，当前长度 j 不可行，就改试它的次长边界 pi[j - 1]；
• 不断回退，直到字符相等或 j == 0。

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

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

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

为什么回退到 pi[j - 1]

当前已有长度 j 的相等前后缀，但新字符无法接在它们后面。任何仍有可能的更短答案，必须同时是这段长度 j 字符的前缀与后缀；其中最长者正是 pi[j - 1]。因此这不是启发式跳转，而是按候选长度从大到小进行完整排除。

注意代码是 pi[j - 1]，不是 pi[i - 1]，也不是简单的 --j。前者沿着“边界的边界”跳转，后者可能逐位退回并退化为二次复杂度。

用 pi 匹配文本

扫描文本时，用 j 表示已经匹配的模式串长度。对当前文本字符 text[i]：

1. 若它与 pattern[j] 不同，就令 j = pi[j - 1]，尝试更短边界；
2. 若字符相同，就令 ++j；
3. 当 j == pattern.size() 时，找到一个起点 i + 1 - pattern.size()；
4. 记录答案后令 j = pi[j - 1]，继续寻找可能重叠的下一次出现。

文本ababai = 2 时第一次完整匹配，起点为 0

匹配后ababaj 从 3 回退到 pi[2] = 1，保留结尾 a

继续ababai = 4 时第二次匹配，起点为 2

完整 C++17 实现

#include <cstddef>
#include <iostream>
#include <string_view>
#include <vector>

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

std::vector<std::size_t> findAll(std::string_view text,
                                 std::string_view pattern) {
    std::vector<std::size_t> positions;

    // 这里采用数学上的约定：空模式匹配每个字符边界。
    if (pattern.empty()) {
        positions.reserve(text.size() + 1);
        for (std::size_t i = 0; i <= text.size(); ++i) {
            positions.push_back(i);
        }
        return positions;
    }

    const std::vector<std::size_t> pi = prefixFunction(pattern);
    std::size_t j = 0;

    for (std::size_t i = 0; i < text.size(); ++i) {
        while (j > 0 && text[i] != pattern[j]) {
            j = pi[j - 1];
        }
        if (text[i] == pattern[j]) {
            ++j;
        }
        if (j == pattern.size()) {
            positions.push_back(i + 1 - pattern.size());
            j = pi[j - 1];  // 保留边界，允许重叠匹配
        }
    }
    return positions;
}

int main() {
    const auto positions = findAll("ababa", "aba");
    for (std::size_t index : positions) {
        std::cout << index << ' ';  // 输出：0 2
    }
}

为什么算法正确

构造 pi 时没有漏掉候选

设当前候选边界长度为 j。若新字符失配，长度 j 不可能成为新边界。任何更短的合法边界都必须是当前边界的边界，因此沿 j = pi[j - 1] 跳转会按从长到短枚举所有可能候选，直到找到能延长的最长者。

匹配时 j 的含义始终成立

扫描到 text[i] 前，j 表示“文本已扫描部分的后缀”与“模式串前缀”相等的最大长度。字符相等时它增长一位；字符失配时，前缀函数把它替换为下一个可能的最大长度。文本中已经扫描的字符不需要重读，所以不变式在每轮后继续成立。

完整匹配一定被报告

当 j 达到模式串长度 m，说明当前文本后缀的 m 个字符与整个模式串相等，起点就是 i + 1 - m。匹配后回退到最长真边界，只丢弃不可能参与下一次匹配的部分，因此重叠答案也不会遗漏。

为什么是 O(n + m)

设文本长度为 n，模式串长度为 m。构造 pi 时，外层下标 i 只向右走；j 每次成功匹配最多增加 1，失配回退则严格减小。所有增加和减小的总次数都是 O(m)，所以预处理为 O(m)。

匹配文本时同理：i 从不回退，j 的增长总次数不超过 n，回退次数也不可能超过此前的增长次数。因此匹配为 O(n)，总时间 O(n + m)，前缀数组占用 O(m) 空间。

pi、next 和 nextval 为什么看起来不同

不同教材常使用不同定义：

它们表达的是同一类前后缀信息，但数组含义和下标约定不完全相同。最常见的错误就是从一份代码拿 next 的构造方式，再配另一份代码的跳转公式。使用模板前，应先用一句话说清数组每个元素究竟表示“长度”还是“下标”。

常见错误

1. 把真前后缀忘掉：整个字符串不能同时作为自己的候选前缀和后缀，否则 pi[i] 会失去回退意义。
2. 失配只回退一次：回退后的候选仍可能失配，所以必须使用 while，不能只写一个 if。
3. 写成 j = pi[i - 1]：回退链由当前候选 j 决定，应写 j = pi[j - 1]。
4. 找到答案后把 j 清零：这样会漏掉 ababa 中两个重叠的 aba；应回退到 pi[j - 1]。
5. 空模式越界：若不提前处理，匹配阶段会访问不存在的 pattern[0]。
6. 混淆字节与字符：std::string_view 按字节比较 UTF-8。纯匹配仍能找到相同字节序列，但返回的是字节下标，不一定是用户看到的字符序号。

前缀函数的其他用途

判断字符串是否由某个短串重复组成

字符串长度为 n，令 candidate = n - pi[n - 1]。若 n % candidate == 0，那么最短循环节长度就是 candidate；否则整个字符串自身才是循环节。

bool isRepeatedPattern(std::string_view s) {
    if (s.empty()) return false;
    const auto pi = prefixFunction(s);
    const std::size_t period = s.size() - pi.back();
    return period < s.size() && s.size() % period == 0;
}

统计每个前缀出现次数

pi 建立了一棵“边界父链”：长度 len 的父边界是 pi[len - 1]。先统计每个 pi[i]，再沿父链从长到短累加，就能求出每个前缀在字符串中作为子串出现了多少次。

建议测试用例

最后的记忆线索

1. pi[i] 是 pattern[0...i] 的最长相等真前后缀长度；
2. 字符相等就让当前匹配长度 j 增加；
3. 字符失配就沿 j = pi[j - 1] 寻找次长边界；
4. 扫描文本时 i 永不回退；
5. 完整匹配后仍沿前缀函数回退，从而保留重叠答案。

KMP 真正解决的不是“怎样更快地比较字符”，而是“失配以后，哪些已知信息仍然有效”。前缀函数把这种信息压缩成一条回退链，因此文本只需从左到右读取一次。