183 lines
7.5 KiB
Markdown
183 lines
7.5 KiB
Markdown
好——我把 **KMP（Knuth–Morris–Pratt）算法** 讲得尽量细致、直观并配上代码与举例，帮助你完全搞清楚它的思想、实现与常见的下标/`next`（或 `pi`）定义差异。
|
||
|
||
# 1) 问题与直观想法
|
||
|
||
目标：在长度为 `n` 的主串 `s` 中查找长度为 `m` 的模式串 `p` 是否出现，并返回第一次出现的位置（下标从 0 开始）。
|
||
朴素做法在遇到失配时会把模式整段右移 1，可能导致重复比较，最坏 `O(n*m)`。
|
||
KMP 的关键：当模式在某个位置发生部分匹配然后失配时，利用已经匹配的信息**不回头重比**，直接把模式滑动到可以继续利用已匹配前缀的位置，从而保证整体复杂度线性 `O(n + m)`。
|
||
|
||
# 2) 前缀函数（prefix function / π 或常说的 next）
|
||
|
||
常用的定义（0 基）——称为 `pi[i]`：
|
||
|
||
> `pi[i]` 表示模式 `p[0..i]`（长度 `i+1`）的 **最长的真前缀（proper prefix）同时也是后缀（suffix）** 的长度。
|
||
|
||
例：若 `p = "ababaca"`，则
|
||
|
||
```
|
||
i: 0 1 2 3 4 5 6
|
||
p: a b a b a c a
|
||
pi: 0 0 1 2 3 0 1
|
||
```
|
||
|
||
解释：例如 `pi[4] = 3` 表示 `p[0..2] == p[2..4] == "aba"`。
|
||
|
||
**注意：** 文献里 `next` 数组有多种约定。有的把 `next[i] = pi[i-1]`，也有的把 `next[i] = pi[i-1] + 1`（1-based 的位置）。务必分清你所用的下标约定。下面我用最常见的 0-based `pi`，它和匹配阶段的 `j = pi[j-1]` 关系最直接。
|
||
|
||
# 3) 如何线性时间构造 `pi`（核心技巧）
|
||
|
||
思路：用已经计算出的 `pi` 值“回退”来扩展新位置，而不是每次从头匹配。
|
||
伪代码（0-based）:
|
||
|
||
```
|
||
pi[0] = 0
|
||
j = 0 // 当前已匹配的长度（也是 p 的下一个比较下标）
|
||
for i = 1 .. m-1:
|
||
while j > 0 and p[i] != p[j]:
|
||
j = pi[j-1] // 回退到较短的已知匹配
|
||
if p[i] == p[j]:
|
||
j += 1
|
||
pi[i] = j
|
||
```
|
||
|
||
时间复杂度：每个 `i` 的 `while` 回退总次数在整个过程是 O(m)（每次回退减少 `j`），所以构造 `pi` 是线性时间 O(m)。
|
||
|
||
# 4) 匹配阶段（利用 `pi`）
|
||
|
||
匹配 `s`（长度 `n`）与 `p`（长度 `m`）：
|
||
|
||
```
|
||
j = 0 // 当前匹配到模式的长度
|
||
for i = 0 .. n-1:
|
||
while j > 0 and s[i] != p[j]:
|
||
j = pi[j-1] // 失配时回退，利用前缀信息
|
||
if s[i] == p[j]:
|
||
j += 1
|
||
if j == m:
|
||
// 找到一次 Occurrence，起始下标 = i - m + 1
|
||
return i - m + 1 // 若只要第一次出现
|
||
// 若想继续找下一个，可 j = pi[j-1]
|
||
```
|
||
|
||
关键：当发生失配时，我们并不是把 `j` 置为 0，而是设置为 `pi[j-1]`（可能为 0 或更小），这样保证不会重新比较已经确认匹配过的字符，从而节省工作。
|
||
|
||
# 5) 小例子演示（一步步算 `pi`，并演示一次匹配失配后的回退）
|
||
|
||
**构造 `pi` 的例子**： `p = "ababaca"`（如上）
|
||
我们已经给出 `pi = [0,0,1,2,3,0,1]`。在 i=5 时（字符 `c`），之前 j=3（表示已匹配 `"aba"`），但 `p[5] != p[3]`，于是回退 `j = pi[2] = 1`，再比较，若仍不等继续回退... 这就是 `while j>0` 的意义。
|
||
|
||
**匹配中的回退示意**：
|
||
取 `s = "ababcababaca"`, `p = "ababaca"`。
|
||
匹配到 `i = 4` 时，可能出现失配（示例中 `s[4] = c`，`p[4] = a`），我们不用把 `i` 回到 `i - j + 1 + 1` 再重新从 `j=0` 开始，而是把 `j` 设为 `pi[j-1]`（例如从 4 回退到 2、再回退到 0），然后继续用当前 `i` 与新 `j` 比较 —— 节省了重复比较已经确认的前缀。
|
||
|
||
# 6) 复杂度与空间
|
||
|
||
* 构建 `pi`：O(m) 时间，O(m) 空间（存 `pi`）。
|
||
* KMP 匹配（一次完整查找）：O(n) 时间（匹配阶段），总共 O(n + m)。
|
||
* 常数空间（除了 `pi` 数组以外）。
|
||
|
||
# 7) 关于 `next` / `pi` 的下标约定（容易混淆）
|
||
|
||
* 我常用的 `pi[i]` 是长度（0-based）。
|
||
* 有些题目/实现中会直接把 `next[j]` 当作“当在模式的第 j 个位置失配时，下次应该从模式的哪个位置继续匹配”的值。
|
||
|
||
* 若问题给的 `j` 是 1-based 的位置，你会看到 `next[j] = pi[j-1] + 1`（把长度变成“1-based 的位置”）。
|
||
* 若问题给的 `j` 是 0-based 的位置或要求输出 `pi[j-1]`，你就按 `pi[j-1]` 输出（这是你之前题目里的做法：`j = m/4, 2m/4, 3m/4`，输出 `pi[j-1]`）。
|
||
总结：**遇到输出/题意时先确认下标是 0-based 还是 1-based，再决定是否要 +1 的位移**。
|
||
|
||
# 8) 对你之前样例的说明（与题目要求的映射）
|
||
|
||
你之前的样例：`p = "abcabcabcabc"`, `m = 12`。
|
||
计算 `pi`（0-based）会得到：
|
||
|
||
```
|
||
pi = [0,0,0,1,2,3,4,5,6,7,8,9]
|
||
```
|
||
|
||
题里要求输出 `j = m/4, 2m/4, 3m/4` 处的值（以他们的约定，要输出 `next[j]` 或 `f[j-1]+1`），在我们用 0-based `pi` 的实现里对应的就是 `pi[j-1]`：
|
||
|
||
* j = 3 -> 输出 `pi[2] = 0`
|
||
* j = 6 -> 输出 `pi[5] = 3`
|
||
* j = 9 -> 输出 `pi[8] = 6`
|
||
正好是样例 `0 3 6`。
|
||
|
||
# 9) 参考实现（C++，带注释 —— 与之前题目输出约定一致）
|
||
|
||
```cpp
|
||
#include <bits/stdc++.h>
|
||
using namespace std;
|
||
|
||
// 构造 pi 数组（0-based）
|
||
vector<int> buildPi(const string &p) {
|
||
int m = (int)p.size();
|
||
vector<int> pi(m, 0);
|
||
int j = 0;
|
||
for (int i = 1; i < m; ++i) {
|
||
while (j > 0 && p[i] != p[j]) j = pi[j - 1];
|
||
if (p[i] == p[j]) ++j;
|
||
pi[i] = j;
|
||
}
|
||
return pi;
|
||
}
|
||
|
||
// KMP 搜索，返回 p 在 s 中首次出现的起始下标（若无返回 -1）
|
||
int kmpSearchFirst(const string &s, const string &p, const vector<int> &pi) {
|
||
int n = (int)s.size(), m = (int)p.size();
|
||
int j = 0;
|
||
for (int i = 0; i < n; ++i) {
|
||
while (j > 0 && s[i] != p[j]) j = pi[j - 1];
|
||
if (s[i] == p[j]) ++j;
|
||
if (j == m) {
|
||
return i - m + 1;
|
||
}
|
||
}
|
||
return -1;
|
||
}
|
||
|
||
int main() {
|
||
ios::sync_with_stdio(false);
|
||
cin.tie(nullptr);
|
||
|
||
string s, p;
|
||
// 读两行（主串和模式串）
|
||
if (!getline(cin, s)) return 0;
|
||
if (!getline(cin, p)) return 0;
|
||
|
||
int m = (int)p.size();
|
||
vector<int> pi = buildPi(p);
|
||
|
||
// j1, j2, j3 分别为 m/4, 2m/4, 3m/4（整除向下）
|
||
int j1 = m / 4;
|
||
int j2 = 2 * m / 4;
|
||
int j3 = 3 * m / 4;
|
||
|
||
auto getVal = [&](int j) -> int {
|
||
if (j <= 0) return 0; // 若 j==0（极小 m 的情况），按题意可以返回 0
|
||
return pi[j - 1]; // 输出 pi[j-1]
|
||
};
|
||
|
||
cout << getVal(j1) << " " << getVal(j2) << " " << getVal(j3) << " \n";
|
||
cout << kmpSearchFirst(s, p, pi) << "\n";
|
||
|
||
return 0;
|
||
}
|
||
```
|
||
|
||
这段代码与我们上面的理论一致：`pi[i]` 存最长相等前后缀长度；对于题里要求的 “在模式串第 j 处失配后下一次匹配的位置” 输出 `pi[j-1]`（当把 `j` 看成从 1 开始的位置时）。我在 `getVal` 中也对 `j <= 0` 做了保护，避免越界（实际在线测评一般 `m >= 4`，但加上保险更稳健）。
|
||
|
||
# 10) 小结与常见坑
|
||
|
||
* 核心在于 **前缀函数 `pi`** 的正确理解和构造；匹配阶段使用 `j = pi[j-1]` 来回退。
|
||
* 小心 **下标约定**（0-based vs 1-based）：很多题把 `next` 定义为 `pi[j-1]` 或 `pi[j-1]+1`，看清题目要求再输出。
|
||
* 边界情况：`m = 0` 或 `m` 非常小要注意越界检查。（通常题目会保证 `m >= 1`。）
|
||
|
||
---
|
||
|
||
如果你愿意我可以：
|
||
|
||
* 把上面的 C++ 程序逐步在一个具体例子上“手动运行”并显示每一步 `i, j, pi` 的变化，帮助你更直观地理解；或
|
||
* 给出一个 Python 版本；或
|
||
* 讲讲 KMP 的一些变体（比如计算全部出现位置、在线流式匹配、或与 Z 算法的比较）。
|
||
|
||
你想先看哪一种？
|