KMP算法 知识点讲解

概念

KMP 算法（Knuth-Morris-Pratt）是字符串匹配领域的一个经典算法。想象一下，你正在玩一个“找茬”游戏：屏幕上有一长串乱码（文本串 $S$），你需要快速找出其中是否包含某个特定的密码串（模式串 $P$），并且要找出所有出现的位置。

最朴素的想法是“暴力比对”：把密码串 $P$ 放在乱码 $S$ 的最左边，逐位比较；如果某一位对不上，就把 $P$ 整体向右移动一位，再从第一位开始重新比。这种方法在密码串很长时效率极低，因为即使前面已经比对了 99 个字符，只要第 100 个对不上，前面那 99 个字符的比对结果就全部作废了，必须从头再来。

KMP 算法的核心思想就是避免这种无谓的回退。它利用了一个关键观察：如果密码串 $P$ 的前缀和某个后缀是相同的（例如 $P=$"ababa"，前缀"aba"和后缀"aba"相同），那么当我们在文本串 $S$ 中匹配到这一长串字符时，如果最后发现失配，我们其实不需要把 $P$ 往回退，也不需要把 $S$ 的指针往回退。我们可以直接利用这个“前缀=后缀”的性质，把 $P$ 向右滑动一段距离，让那个相等的后缀去接着和 $S$ 里已经匹配好的部分对齐，从而跳过大量重复的比较。

为了量化这种“前缀=后缀”的长度，我们引入了一个数组，通常称为 next 数组（或前缀函数）。next[j] 的值表示：在模式串 $P$ 的前 $j$ 个字符（即 $P[0..j-1]$）中，最长的、既是该前缀的真前缀又是其真后缀的子串长度。

触发清单（看到这些信号第一时间想到本知识点）

定义

next 数组（前缀函数 / 失配函数）：next[j] 表示「模式串 P[0..j-1] 这个前缀里，最长的、相等的『真前缀 = 真后缀』的长度」。换句话说，next[j] 就是 P[0..j-1] 的最长公共前后缀长度。

匹配规则：用 i 扫 S、j 扫 P。当 S[i] == P[j] 时 i++、j++；一旦 S[i] != P[j] 且 j>0，就令 j = next[j]（模式串右移到「能接上的最长前缀」继续比），i 不动；当 j == m 说明找到一次完整匹配，记录位置后令 j = next[j] 继续找下一处。

next 自身怎么求：next 数组本质上是「模式串和自己匹配」。用两个指针 i（后缀尾）、j（前缀尾，j 同时就是 next[i] 的候选），逻辑和上面匹配完全同构，边扫边填。

复杂度：求 next 一遍 O(m)，匹配一遍 O(n)，合计 O(n+m)；空间 O(m)。

两大派生结论：

• 若 m % (m - next[m]) == 0，则 P 的最小循环节长度为 m - next[m]（字符串周期）。
• next 链能统计所有 border（既是前缀又是后缀的子串）。

为什么 i 不回退也不会漏匹配？ 设当前在 S[i] 处失配，说明 P[0..j-1] 已经和 S[i-j..i-1] 完全相等。KMP 把 j 跳到 next[j]，而 next[j] 的语义正是「P[0..j-1] 里最长的相等前后缀长度」——也就是说，把 P 右移 j - next[j] 位后，P[0..next[j]-1] 必然已经和 S[i-next[j]..i-1] 对齐相等。既然这一段本来就相等，当然不用再比，直接从 S[i] 接着比 P[next[j]]。任何「更小右移量」都会因为前后缀不等而必然失配，所以只跳 next[j] 既不会漏、也不会多做无用功。

为什么是 O(n+m)？ 每执行一次 i++，j 至多 +1；每执行一次 j = next[j]（跳回），j 严格变小。因此 i + j 这个量单调不降、且上限为 n + m，整个匹配过程的「前进 + 回跳」总步数被 n + m 兜住，平摊 O(1) 每步。

它能用来干什么：除了「找子串位置」，KMP 的 next 链天然能回答「字符串周期 / 最小循环节 / 所有 border 长度」。很多看似和匹配无关的题，本质都是在问 next[m] 或整条 next 链的性质。

例题

题目描述

给定两个字符串 $S$ 和 $P$，其中 $S$ 是文本串，$P$ 是模式串。请输出 $P$ 在 $S$ 中所有出现的起始位置（下标从 1 开始），以及 $P$ 每个前缀的 next 值。

输入格式：

第一行包含两个整数 $n, m$，分别表示 $S$ 和 $P$ 的长度。

第二行包含字符串 $S$。

第三行包含字符串 $P$。

输出格式：

第一行输出 $P$ 在 $S$ 中所有出现位置的起始下标，用空格分隔。

第二行输出 $P$ 每个前缀（长度为 $1$ 到 $m$）的 next 值，用空格分隔。

数据范围：

$1 \le n, m \le 10^5$，字符串仅包含小写字母。

审题分析

1. 读题抓条件：需要找出所有出现位置（意味着可能有重叠，如 $S=$"aaaa"，$P=$"aa"，位置应为 1, 2, 3）；需要输出每个前缀的 next 值。

2. 定需求：核心需求是字符串匹配，且要求线性时间复杂度（因为 $n, m$ 可达 $10^5$，暴力 $O(nm)$ 会超时）。

3. 为什么能用本知识点：KMP 算法正是为了解决这种“找所有出现位置”且要求高效的问题而设计的。它的核心就是利用 next 数组跳过不必要的比较。

4. 如果不用会怎样：如果不使用 KMP，对于 $S=$"aaaa...a"（$10^5$ 个 a）和 $P=$"aa"，暴力匹配会导致 $O(nm)$ 次比较，即 $10^{10}$ 次操作，远超 1 秒时限。

解题思路

1. 预处理 next 数组：对模式串 $P$ 调用 KMP 的预处理函数，计算出 next[1..m]。注意 next[0] 通常定义为 0。

2. 匹配过程：

- 初始化文本串指针 $i=0$，模式串指针 $j=0$。

- 循环遍历文本串 $S$（$i$ 从 $0$ 到 $n-1$）：

- 如果 $S[i] == P[j]$，则 $i++$，$j++$。

- 如果 $j == m$，说明找到一次完整匹配。记录起始位置 $i - m + 1$（因为题目要求下标从 1 开始）。然后关键一步：$j = next[j]$，继续寻找下一处（允许重叠）。

- 如果 $S[i] != P[j]$ 且 $j > 0$，则 $j = next[j]$（利用 next 数组跳回最长公共前后缀）。

- 如果 $S[i] != P[j]$ 且 $j == 0$，则 $i++$（文本串指针前进，模式串从头开始比）。

3. 输出：先输出所有匹配位置，再输出 next 数组。

C++ 完整参考代码

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

using namespace std;

// 计算 next 数组
// nxt[i] 表示 P[0..i-1] 的最长公共前后缀长度
vector<int> getNext(const string& p) {
 int m = p.size();
 vector<int> nxt(m + 1, 0); // nxt 多开一位，nxt[0]=0
 // i 是后缀尾，j 是前缀尾（同时 nxt[i] 的候选）
 for (int i = 1, j = 0; i < m; ) {
 if (p[i] == p[j]) {
 nxt[++i] = ++j; // 相等：前后缀都拉长
 } else if (j) {
 j = nxt[j]; // 不等：前缀指针回跳
 } else {
 ++i; // j==0 且不等：i 前进
 }
 }
 return nxt;
}

// KMP 匹配
// 返回所有匹配起始位置（下标从 1 开始）
vector<int> kmp(const string& s, const string& p) {
 int n = s.size(), m = p.size();
 auto nxt = getNext(p);
 vector<int> pos;
 for (int i = 0, j = 0; i < n; ) {
 if (s[i] == p[j]) {
 ++i; ++j;
 }
 if (j == m) {
 pos.push_back(i - m + 1); // 记录 1-based 位置
 j = nxt[j]; // 关键：继续找下一处（含重叠）
 } else if (i < n && s[i] != p[j]) {
 if (j) j = nxt[j]; // 失配：只移动模式串
 else ++i; // j==0 仍不等：主串前进
 }
 }
 return pos;
}

int main() {
 int n, m;
 cin >> n >> m;
 string s, p;
 cin >> s >> p;

 // 1. 求 next 数组并输出
 auto nxt = getNext(p);
 for (int i = 1; i <= m; ++i) {
 cout << nxt[i] << (i == m ? "" : " ");
 }
 cout << endl;

 // 2. 匹配并输出位置
 auto pos = kmp(s, p);
 for (int i = 0; i < pos.size(); ++i) {
 cout << pos[i] << (i == pos.size() - 1 ? "" : " ");
 }
 cout << endl;

 return 0;
}

代码解读

• getNext 函数：核心逻辑是“模式串自己和自己比”。i 代表当前正在比较的后缀末尾，j 代表当前匹配的前缀末尾。当 p[i] == p[j] 时，说明前后缀都延长了，nxt[++i] = ++j；当不等且 j > 0 时，利用 nxt[j] 跳回最长公共前后缀；当 j == 0 且不等时，只能让后缀末尾 i 前进。
• kmp 函数：i 扫文本串，j 扫模式串。相等则双指针前进；匹配完整（j == m）时记录位置并 j = nxt[j]（注意这里不能重置 j=0，否则会漏掉重叠匹配）；失配时若 j > 0 则 j = nxt[j]，否则 i++。
• main 函数：先输出 next 数组（从 1 到 m），再输出匹配位置。

运行结果（输入：n=10, m=4, S=ababababab, P=abab）：

0 1 0 2
1 3 5 7

（第一行是 next 数组：next[1]=0, next[2]=1, next[3]=0, next[4]=2；第二行是匹配位置：1, 3, 5, 7）

例题复盘总结

本模块仅有一道例题（洛谷 P3375【模板】KMP），其核心考点非常集中：

• 共性特征：要求输出所有出现位置（含重叠）+ 输出 next 数组。
• 各自技巧：

- next 数组计算必须用“模式串自匹配”的写法，注意 nxt 多开一位，nxt[0]=0。

- 匹配时找到一次后必须 j = nxt[j] 而不是 j = 0，这是处理重叠的关键。

- 输出位置时注意题目要求的下标是从 1 开始还是从 0 开始，本题要求 1-based，所以记录 i - m + 1。

• 审题模板：看到“所有出现位置”先想 KMP；看到“next 数组”直接调用 getNext；看到“重叠”检查 j = nxt[j] 是否写对。
• 错误清单：

- i 回退：失配时写成 i-- 重来，退化成 O(nm)。记住 i 只增不减。

- next 定义差一错误：到底是「next[j] = 长度为 j 的前缀的最长 border」，还是「next[i] 对应 P[i] 失配时跳哪」？统一用「next[j] = P[0..j-1] 的最长公共前后缀长度」这一条，代码就不会乱。

- 找到匹配后重置 j=0：会丢掉重叠匹配。正确是 j = next[j]。

- 下标从 0 还是 1：输出位置、边界判断都受此影响，样例没过先查这个。

- 循环节题忘了判整除：m - next[m] 是候选长度，但只有当 m % (m-next[m]) == 0 时才是「完整由循环节重复构成」；否则最小循环节就是 m 本身（无更短周期）。

- 边界别漏：空串 / 单字符 / next[0]=0 的初始化，以及找到匹配后「继续用 next[j] 而非 j=0」是高频失分点。

写法总表

分工说明：「触发清单」告诉你什么时候用 KMP（看到匹配、周期、border 信号）；「技巧速查表」告诉你怎么背核心结论（next 定义、匹配规则、周期公式）；「写法总表」告诉你代码层面如何分层实现（求 next、匹配、周期）。

常见错误

1. i 回退：失配时写成 i-- 重来，退化成 O(nm)。记住 i 只增不减。

2. next 定义差一错误：到底是「next[j] = 长度为 j 的前缀的最长 border」，还是「next[i] 对应 P[i] 失配时跳哪」？统一用「next[j] = P[0..j-1] 的最长公共前后缀长度」这一条，代码就不会乱。

3. 找到匹配后重置 j=0：会丢掉重叠匹配。正确是 j = next[j]。

4. 循环节题忘了判整除：m - next[m] 是候选长度，但只有当 m % (m-next[m]) == 0 时才是「完整由循环节重复构成」；否则最小循环节就是 m 本身（无更短周期）。

5. 下标从 0 还是 1：输出位置、边界判断都受此影响，样例没过先查这个。

自测

• 口述：为什么 j = next[j] 后，P[0..next[j]-1] 一定已经和主串对齐相等，无需重比？
• 计算：模式串 ababa 的 next 数组分别是多少？（答案：0,0,1,2,3）
• 判断：串 abcabcabc 的最小循环节是什么？长度多少？（答案：循环节 abc，长度 3）
• 变形：若要求「每个前缀最长的不与前缀自身重叠的 border 长度」，对 ababa 你会怎么沿 next 链跳？（一直跳到 <= 长度/2 的 border）

举一反三 · 审题流水线

1. 看到“所有出现位置” → 先想 KMP，确认是否需要处理重叠（若不需要重叠，匹配完重置 j=0 即可）。

2. 看到“next 数组” → 直接调用 getNext，注意 nxt 多开一位，nxt[0]=0。

3. 看到“周期”或“既是前缀又是后缀” → 用 m - next[m] 判断，记得判整除。

4. 看到“border 计数”或“动物园” → 沿 next 链跳，预处理 cnt 或在链上跳到阈值（如 > len/2 截断）。

5. 看到数据范围 $10^5$ 且要求线性 → 排除暴力 $O(nm)$，锁定 KMP 或 Z 算法。

练手题

题一：重叠匹配计数

给定字符串 $S$ 和模式串 $P$，求 $P$ 在 $S$ 中所有出现位置的个数（允许重叠）。例如 $S=$"aaaa"，$P=$"aa"，答案应为 3（位置 1, 2, 3）。

提示：直接套用 KMP 匹配函数，找到一次后 j = nxt[j] 继续，统计次数即可。

题二：最小循环节验证

给定字符串 $T$，判断它是否由某个更短的字符串重复若干次构成。若是，输出该最短重复串；若不是，输出 $T$ 本身。

提示：计算 len = T.size()，L = len - next[len]。若 len % L == 0，则最小循环节长度为 L，重复串为 T.substr(0, L)；否则最小循环节就是 $T$ 本身。