KMP 与前缀函数 (Knuth-Morris-Pratt)

KMP 算法用于在主串 \(T\) 中高效检索模式串 \(P\) 的所有出现位置。其核心在于预计算模式串的前缀函数 (Prefix Function，常记为 \(\pi\) 或 next 数组)。

时间复杂度：预处理 \(\mathcal{O}(|P|)\)，匹配 \(\mathcal{O}(|T|)\)。

---

前缀函数与匹配模版

前缀函数 \(\pi[i]\) 定义为子串 \(s[0 \dots i]\) 最长的真前缀长度，使得该真前缀同时是该子串的真后缀。

#include <vector>
#include <string>

// 计算字符串 s 的前缀函数 pi
std::vector<int> prefix_function(const std::string &s) {
    int n = s.size();
    std::vector<int> pi(n, 0);
    for (int i = 1; i < n; ++i) {
        int j = pi[i - 1];
        while (j > 0 && s[i] != s[j]) {
            j = pi[j - 1];
        }
        if (s[i] == s[j]) {
            j++;
        }
        pi[i] = j;
    }
    return pi;
}

// 在文本串 text 中查找模式串 pattern 的所有起始下标 (0-indexed)
std::vector<int> kmp_search(const std::string &text, const std::string &pattern) {
    if (pattern.empty()) return {};
    std::vector<int> pi = prefix_function(pattern);
    std::vector<int> matches;

    int j = 0; // 当前在 pattern 中匹配的长度
    for (int i = 0; i < (int)text.size(); ++i) {
        while (j > 0 && text[i] != pattern[j]) {
            j = pi[j - 1];
        }
        if (text[i] == pattern[j]) {
            j++;
        }
        if (j == (int)pattern.size()) {
            matches.push_back(i - (int)pattern.size() + 1);
            j = pi[j - 1]; // 寻找下一个可能匹配
        }
    }
    return matches;
}

---

常用性质：字符串最小循环周期

对于长度为 \(n\) 的字符串 \(s\)（\(0\)-indexed），令 \(L = n - \pi[n - 1]\)：

• 若 \(n \bmod L == 0\) 且 \(\pi[n - 1] > 0\)，则 \(s\) 具有长度为 \(L\) 的完全循环节，循环次数为 \(n / L\)。
• 无论是否整除，\(L\) 均为 \(s\) 的最小周期。

---

KMP 经典应用好题精选

KMP 绝不仅仅局限于简单的子串匹配。在算法竞赛中，考查最多的是 前缀函数（\(\pi\) / next 数组）的递推性质、Border 树（前缀树链）以及将 KMP 抽象为状态机（DFA）结合 DP。

题型一：Border 链与子串出现判定

Codeforces 126B - Password

题意：给定字符串 \(s\)（\(|s| \le 10^6\)），寻找一个最长的子串 \(t\)，满足： 1. \(t\) 是 \(s\) 的前缀； 2. \(t\) 是 \(s\) 的后缀； 3. \(t\) 在 \(s\) 的中间（不包含首尾）至少完整出现过一次。 若不存在满足条件的子串，输出 Just a legend。

思路解析

• 一个字符串既是前缀又是后缀，称为该字符串的 Border。\(s\) 的所有 Border 长度依次为：\(\pi[n - 1], \pi[\pi[n - 1] - 1], \pi[\pi[\pi[n - 1] - 1] - 1], \dots\)。

• 最长候选长度即为 \(L = \pi[n - 1]\)：

• 如果 \(L = 0\)，直接无解；
• 检查在中间部分（即下标 \(1 \le i \le n - 2\)）是否存在某个位置满足 \(\pi[i] == L\)。若存在，则长度为 \(L\) 的 Border 必定在中间出现过，直接输出前缀 \(s[0 \dots L - 1]\)；
• 若中间没有出现过 \(L\)，则尝试次长 Border \(L' = \pi[L - 1]\)。由于 \(L'\) 既是 \(s[0 \dots L - 1]\) 的前缀又是后缀，而长度为 \(L\) 的前缀就出现在 \(s\) 开头，因此 \(L'\) 必然已经在 \(s\) 中间作为 \(s[0 \dots L - 1]\) 的后缀出现过了！故只要 \(L' > 0\) 则 \(s[0 \dots L' - 1]\) 即为答案，否则无解。

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

void solve() {
    std::string s;
    if (!(std::cin >> s)) return;
    int n = s.size();

    // 1. 计算 pi 数组
    std::vector<int> pi(n, 0);
    for (int i = 1; i < n; ++i) {
        int j = pi[i - 1];
        while (j > 0 && s[i] != s[j]) j = pi[j - 1];
        if (s[i] == s[j]) j++;
        pi[i] = j;
    }

    int len = pi[n - 1];
    if (len == 0) {
        std::cout << "Just a legend\n";
        return;
    }

    // 2. 检查中间 [1, n - 2] 是否存在 pi[i] == len
    bool found_in_middle = false;
    for (int i = 1; i < n - 1; ++i) {
        if (pi[i] == len) {
            found_in_middle = true;
            break;
        }
    }

    if (found_in_middle) {
        std::cout << s.substr(0, len) << "\n";
    } else {
        // 退而求其次，取次长 border
        int next_len = pi[len - 1];
        if (next_len > 0) {
            std::cout << s.substr(0, next_len) << "\n";
        } else {
            std::cout << "Just a legend\n";
        }
    }
}

---

题型二：统计每个前缀的出现次数

Codeforces 432D - Prefixes and Suffixes

题意：给定字符串 \(s\)（\(|s| \le 10^5\)），找出所有既是 \(s\) 的前缀又是 \(s\) 的后缀的子串，并统计它们分别在原串 \(s\) 中作为连续子串出现了多少次。

思路解析

1. 求所有合法的长度：依然通过跳 \(\pi\) 链：\(len = n, \pi[n - 1], \pi[\pi[n - 1] - 1], \dots\) 收集所有前后缀。

2. 统计出现次数：

3. 定义 cnt[i] 为长度为 \(i\) 的前缀出现的次数。初值每个前缀 \(s[0 \dots i - 1]\) 至少在自身位置出现一次，故令 cnt[i] = 1。

4. 每个前缀 \(s[0 \dots i - 1]\) 的最长公共前后缀为 \(\pi[i - 1]\)，这意味着长度为 \(\pi[i - 1]\) 的前缀也在此处完整出现了一次。

5. 因此从后往前（\(i\) 从 \(n\) 递减到 \(1\)），做前缀树的反向拓扑传递：\(\text{cnt}[\pi[i - 1]] \mathrel{+}= \text{cnt}[i]\)；

6. 最终即可在 \(\mathcal{O}(n)\) 时间内得到所有前缀在全串中的出现次数。

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

void solve() {
    std::string s;
    if (!(std::cin >> s)) return;
    int n = s.size();

    std::vector<int> pi(n, 0);
    for (int i = 1; i < n; ++i) {
        int j = pi[i - 1];
        while (j > 0 && s[i] != s[j]) j = pi[j - 1];
        if (s[i] == s[j]) j++;
        pi[i] = j;
    }

    // cnt[i] 统计前缀长度为 i 的出现频次
    std::vector<int> cnt(n + 1, 1);
    for (int i = n; i >= 1; --i) {
        if (pi[i - 1] > 0) {
            cnt[pi[i - 1]] += cnt[i];
        }
    }

    // 收集所有既是前缀又是后缀的长度
    std::vector<std::pair<int, int>> ans;
    for (int len = n; len > 0; len = pi[len - 1]) {
        ans.push_back({len, cnt[len]});
    }
    std::reverse(ans.begin(), ans.end());

    std::cout << ans.size() << "\n";
    for (auto &[len, c] : ans) {
        std::cout << len << " " << c << "\n";
    }
}

---

题型三：回文前缀转化技巧

LeetCode 214 - 最短回文串 (Shortest Palindrome)

题意：在给定字符串 \(s\) 的前方添加最少数量的字符，将其转换为回文串。

思路解析

• 在 \(s\) 前方添加最少字符，等价于寻找 \(s\) 的最长回文前缀。设最长回文前缀长度为 \(L\)，将 \(s\) 在 \(L\) 之后的后缀翻转后拼到最前方即可。
• 判断 \(s\) 的前缀是否为回文串：将 \(s\) 翻转得到 \(s_{\text{rev}}\)。若 \(s\) 的某个前缀等于 \(s_{\text{rev}}\) 的某个后缀，则该前缀必为回文串。
• 构造辅助串：\(T = s + \# + s_{\text{rev}}\)。计算 \(T\) 的前缀函数 \(\pi\)。由于中间加入了分隔符 \(\#\) 防止越界，\(\pi[|T| - 1]\) 的值恰好就是 \(s\) 与 \(s_{\text{rev}}\) 后缀的最长匹配长度，即 \(s\) 的最长回文前缀长度！

#include <string>
#include <vector>
#include <algorithm>

std::string shortestPalindrome(std::string s) {
    if (s.empty()) return "";
    std::string rev = s;
    std::reverse(rev.begin(), rev.end());

    std::string t = s + "#" + rev;
    int m = t.size();
    std::vector<int> pi(m, 0);

    for (int i = 1; i < m; ++i) {
        int j = pi[i - 1];
        while (j > 0 && t[i] != t[j]) j = pi[j - 1];
        if (t[i] == t[j]) j++;
        pi[i] = j;
    }

    int max_pal_len = pi[m - 1];
    std::string to_add = s.substr(max_pal_len);
    std::reverse(to_add.begin(), to_add.end());
    return to_add + s;
}

---

题型四：KMP 转移图与矩阵快速幂 DP

HNOI2008 / 洛谷 P3193 - GT考试

题意：求长度为 \(n\)（\(n \le 10^9\)）且不包含给定长度为 \(m\)（\(m \le 20\)）的不吉利数字串 \(P\) 的数字字符串数量，结果对 \(K\) 取模。

思路解析

• \(n \le 10^9\) 且模式串极小（\(m \le 20\)），是极典型的 状态机 + 矩阵快速幂加速 DP。
• 将模式串 \(P\) 预处理出 KMP 自动机的转移表：trans[u][c] 表示当前在模式串已匹配了 \(u\) 个字符，下一个输入的数字为 \(c \in [0, 9]\) 时，状态转移到多少。
• 构建一个 \(m \times m\) 的转移矩阵 \(A\)：其中 \(A[u][v]\) 表示从状态 \(u\) 输入单个字符能转移到状态 \(v\) 的字符数（\(v < m\)，不可到达终态 \(m\)）。
• 最终合法串的方案数即为矩阵 \(A^n\) 的第 \(0\) 行所有元素之和，利用矩阵快速幂在 \(\mathcal{O}(m^3 \log n)\) 时间内完成计算。

---

推荐练习题单

题目	平台	核心考点	难度
POJ 2406 Power Strings	POJ / 洛谷	最小循环节与 \(\pi[n-1]\) 整除性判定	普及+/提高
CF 126B Password	Codeforces	Border 树判定与中间出现判断	提高+/省选-
CF 432D Prefixes and Suffixes	Codeforces	前缀出现频次拓扑计数 DP	提高+/省选-
LeetCode 214 最短回文串	LeetCode	拼串求最长回文前缀技巧	困难
洛谷 P3435 [POI2006] OKR-Periods of Words	洛谷 / POI	树上倍增/并查集压缩求解最小 Border	提高+/省选-
洛谷 P3193 [HNOI2008] GT考试	洛谷 / HNOI	KMP 自动机转移图 + 矩阵快速幂 DP	省选/NOI-

---

LeetCode 经典真题精选与题解提示

• LeetCode 28 - 找出字符串中第一个匹配项的下标 (Find the Index of the First Occurrence in a String) 简单

  提示

  单模式串匹配标准模板题。

  • 计算模式串 \(needle\) 的前缀函数数组 \(\pi\)。
  • 维护主串指针 \(i\) 与模式串指针 \(j\) 进行线性扫描。当匹配失败时，利用 \(j = \pi[j - 1]\) 快速回退，实现 \(\mathcal{O}(N + M)\) 线性时间匹配。

• LeetCode 459 - 重复的子字符串 (Repeated Substring Pattern) 简单

  提示

  KMP 周期性引理 (Periodicity Lemma)。

  • 计算全串 \(s\) 的前缀函数 \(\pi\)。设串长为 \(n\)，\(k = \pi[n - 1]\)。
  • 若 \(k > 0\) 且 \(n \bmod (n - k) == 0\)，则 \(n - k\) 必为 \(s\) 的最小循环节长度，原字符串可由其重复多次构成；否则必然不能。

• LeetCode 1392 - 最长快乐前缀 (Longest Happy Prefix) 困难

  提示

  前缀函数（Border）定义直观考查。

  • 题目所定义的“快乐前缀”正是经典字符串理论中的 Border（既是非全串的前缀，又是后缀）。
  • 求全串的前缀函数数组 \(\pi\)，最长快乐前缀长度恰好等于 \(\pi[n - 1]\)，直接返回前缀子串 \(s[0 \dots \pi[n - 1] - 1]\)。

• LeetCode 214 - 最短回文串 (Shortest Palindrome) 困难

  提示

  拼串求最长回文前缀。

  • 在前缀添加最少字符等价于求原串 \(s\) 的最长回文前缀。
  • 构造辅助串 \(T = s + \# + s_{\text{rev}}\)（\(\#\) 为原串中未出现的隔离符）。对 \(T\) 计算前缀函数，\(\pi[|T| - 1]\) 即为 \(s\) 的最长回文前缀长度。