KMP：前缀函数与线性字符串匹配｜算法讲义

问题#

给定长度为 $n$ 的文本串 text 和长度为 $m$ 的模式串 pattern，找出模式串在文本中的所有出现位置，允许出现位置相互重叠。

朴素匹配从每个文本位置重新比较，最坏需要 $O(nm)$ 。KMP 的目标是：失配时不让文本指针回退，而是利用已经匹配部分的前后缀信息调整模式串位置。

核心思想与不变量#

前缀函数#

对字符串 $s$ ，定义：

\pi[i]=\max\{k\mid 0\le k<i+1,\ s[0,k)=s[i-k+1,i+1)\}.

也就是说，pi[i] 是前缀 s[0..i] 的最长相等真前缀与后缀的长度。例如 s = "ababaca" 的前缀函数为：

s:  a b a b a c a
pi: 0 0 1 2 3 0 1

计算 pi[i] 时，先令 j = pi[i-1]。如果 s[i] != s[j]，长度为 j 的候选边界失败；下一个仍可能成立的最长候选，正是这个边界自身的最长边界 pi[j-1]。不断跳转，直到字符相等或 j = 0。

循环不变量是：每次比较前，s[0,j) 已经等于 s[i-j,i)，而 j 是尚未排除的最长候选边界。

匹配过程#

扫描文本时令 j 表示当前已经匹配的模式串前缀长度。若 text[i] 与 pattern[j] 失配，同样令 j = pi[j-1]；若匹配则 j++。

当 j == m，一次匹配结束于位置 i，起点是 i-m+1。记录答案后不能直接清零，而要令 j = pi[j-1]，这样才能发现重叠匹配。

文本指针始终只向右移动；模式长度 j 虽会回退，但每次增长和回退的总次数都是线性的。

复杂度#

构造长度为 $m$ 的前缀函数需要 $O(m)$ 时间和 $O(m)$ 空间；扫描长度为 $n$ 的文本需要 $O(n)$ 时间。因此总时间为 $O(n+m)$ ，额外空间为 $O(m)$ 。

虽然代码含有嵌套 while，但 j 每增长一次才有可能在之后回退一次，所有回退次数之和不超过所有增长次数之和，因此不是平方复杂度。

C++17 模板#

模板不依赖拼接分隔符，因此文本与模式串可以包含任意普通字符。这里约定空模式串不执行匹配，返回空位置集合。

#include <iostream>
#include <string>
#include <vector>

using namespace std;

vector<int> prefix_function(const string& pattern) {
    vector<int> pi(pattern.size(), 0);
    for (int i = 1; i < static_cast<int>(pattern.size()); ++i) {
        int matched = pi[i - 1];
        while (matched > 0 && pattern[i] != pattern[matched]) {
            matched = pi[matched - 1];
        }
        if (pattern[i] == pattern[matched]) ++matched;
        pi[i] = matched;
    }
    return pi;
}

vector<int> kmp_find_all(const string& text, const string& pattern) {
    vector<int> positions;
    if (pattern.empty()) return positions;

    vector<int> pi = prefix_function(pattern);
    int matched = 0;

    for (int i = 0; i < static_cast<int>(text.size()); ++i) {
        while (matched > 0 && text[i] != pattern[matched]) {
            matched = pi[matched - 1];
        }
        if (text[i] == pattern[matched]) ++matched;

        if (matched == static_cast<int>(pattern.size())) {
            positions.push_back(i - static_cast<int>(pattern.size()) + 1);
            matched = pi[matched - 1]; // 保留边界，继续寻找重叠匹配
        }
    }
    return positions;
}

// 返回能够完整平铺字符串的最短重复单元长度；不存在更短单元时返回 n。
int smallest_repeating_period(const string& text) {
    if (text.empty()) return 0;
    vector<int> pi = prefix_function(text);
    int candidate = static_cast<int>(text.size()) - pi.back();
    return text.size() % candidate == 0 ? candidate : static_cast<int>(text.size());
}

int main() {
    string text = "ababcabcabababd";
    string pattern = "ababd";

    vector<int> positions = kmp_find_all(text, pattern);
    cout << "matches (0-based):";
    for (int position : positions) cout << ' ' << position;
    cout << '\n';

    cout << "period of abcabcabc = "
         << smallest_repeating_period("abcabcabc") << '\n';
    return 0;
}

示例#

模板输出：

matches (0-based): 10
period of abcabcabc = 3

当模式串已经匹配了 abab，却遇到不等于 d 的字符时，KMP 不会把文本位置退回开头，而是沿前缀函数跳到模式串中仍与已读文本后缀相等的最长前缀，再继续比较。

重叠匹配同样能被找到：文本 aaaaa、模式 aaa 的答案为 0, 1, 2。

易错点#

pi[i] 记录的是长度，不是下标；回退写成 pi[matched - 1]，不能访问 pi[matched]。
只有 matched > 0 时才能继续回退，否则会访问负下标。
完整匹配后要先记录位置，再回退到 pi[m-1]；不回退会在下一字符访问 pattern[m]，清零则会漏掉重叠匹配。
next 数组有多种下标和初值约定。使用别人的模板前，应先确认它表示长度还是失配后的下标；本文统一使用前缀函数 pi。
最短边界周期 $n-\pi[n-1]$ 不一定能完整平铺字符串；求重复单元时还要检查 n % candidate == 0。
通过 pattern + '#' + text 计算时，必须保证分隔符不会出现在任一字符串中；流式模板没有这个限制。

课程内应用与延伸阅读#

课程内的前缀信息应用#

沿 pi[n-1]、pi[pi[n-1]-1]... 跳转，可以枚举一个字符串的所有 border（相等真前后缀）。
最短重复单元可由 n - pi[n-1] 得到候选长度，再检查它能否整除字符串长度；正文模板已经实现这一应用。

问题#