字符串匹配最容易被背成一段 while 循环。真正值得理解的是：已经匹配的部分失败后，哪些信息仍然成立，下一次比较应该从哪里继续？

这一篇先建立前缀函数，再用三道题逐步改变任务：找一个还在内部出现的前后缀、统计所有前后缀的出现次数、把数值序列的整体平移变成精确匹配。第三题也能接回前缀和与差分，说明 KMP 不只处理字母。

三道题各自多要求什么

题名、难度、标签与约束于 2026-10-03 核对官方题目页。难度是题库标记，不是本篇阅读顺序必须严格递增的承诺。以下只重新概括目标，不复刻题面故事。

题目与官方入口 难度 主要约束 本篇关注点
126B Password 1700 1 ≤ n ≤ 10^6，小写英文字母 最长合法边界和内部出现
432D Prefixes and Suffixes 2000 1 ≤ n ≤ 10^5，大写英文字母 沿失败链接汇总出现次数
471D MUH and Cube Walls 1800 1 ≤ n,w ≤ 2×10^5；高度在 1 到 10^9 差分消去统一高度偏移
题号 官方标签
126B binary search、dp、hashing、string suffix structures、strings
432D dp、string suffix structures、strings、two pointers
471D string suffix structures、strings

标签表示可行思路的集合，不要求把每个标签都用一遍。下面三份实现均是确定性的线性方法，不依赖哈希碰撞概率。

前缀函数保存的是长度

统一使用从 0 开始的下标。pi[i] 是子串 s[0..i] 的最长真前缀与后缀相等的长度。“真”表示不能取整个 s[0..i]，但前缀和后缀允许重叠。这种同时出现在两端的字符串称为 border，下文叫“边界”。它不是区间的左右端点。

以 ababcabab 为例：

i s[i] s[0..i] 的最长边界 pi[i]
0 a 空 0
1 b 空 0
2 a a 1
3 b ab 2
4 c 空 0
5 a a 1
6 b ab 2
7 a aba 3
8 b abab 4

计算新位置 i 时，先令 j=pi[i−1]。已知前面的长度 j 既是前缀，也是刚读过部分的后缀。如果 s[i]=s[j]，两边都可延长一位；如果不同，就不能保留整个 j，但它自己的最长边界 pi[j−1] 仍可能接上新字符。

为什么不尝试 j−1、j−2 的所有长度？因为候选必须已经是已匹配部分的边界，否则即使最后一个字符相同，前面也对不上。失败链接一次跳到下一个仍有可能的长度。

例如读到上表的 c 时，j 原为 2，尝试接在 ab 后失败，于是退到 pi[1]=0；c 也不等于 a，结果为 0。不是把文本指针退回去重读。

为什么总时间仍然线性

外层每次读一个新字符，j 最多增加 1；while 中每次回退都让 j 严格变小。把 j 看作非负势能：总下降量不超过总上升量，因此整趟扫描中回退次数为 O(n)，不是每个位置都独立支付 O(n)。前缀函数占 O(n) 空间。

这个论证也适用于之后的 KMP 文本扫描：保留“已匹配前缀同时是当前文本后缀”的不变量，失配时仅缩短模式状态，文本仍然只向前走。

第一题 126B 内部出现不能拿末尾冒充

目标是找到最长的字符串 t：它既是整串的前缀，又是整串的后缀，而且还在严格内部出现一次。内部出现的起点必须大于 0，终点必须小于 n−1；三次出现可以重叠。没有答案时输出 Just a legend。

如果枚举所有长度，再逐位置比较字符，重复字符串会带来大量重复工作。前缀函数已经把“哪些长度是整串边界”组织成一条链：

从 L=pi[n−1] 出发，下一项是 pi[L−1]，继续直到 0。它包含所有非空真边界，并且长度严格递减。

用内部最大值判定一条边界

先计算 M=max(pi[0],…,pi[n−2])，空范围的最大值取 0。特意不纳入最后一个位置，因为在那里找到的是末尾出现。

对于整串边界长度 L，存在严格内部出现，当且仅当 L≤M。

必要性：若长度 L 的前缀在内部、以位置 i 结束，那么 L≤i，因为起点不能为 0。因此它是 s[0..i] 的真边界，pi[i]≥L，且 i≤n−2。

充分性：若某个 i≤n−2 有 pi[i]=k≥L，那么该位置前的一个长度 k 的后缀等于整串前缀。取这段后缀的前 L 个字符，就得到所需前缀的一次出现；其起点 i−k+1≥1，终点不超过 i≤n−2，确实位于内部。这里不要求它恰好结束在 i。

于是沿整串边界链向下走，找到第一个不超过 M 的长度，就是最长答案。

手算 s=aaaaa 数值或结论
pi 0，1，2，3，4
不含最后位置的 M 3
首个候选 L=4 太长；只有开头和末尾两次
回退到 L=3 合法；起点 0、1、2 各出现一次
最终答案 aaa，重叠不影响合法性

完整 C++17 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    cin >> s;
    int n = static_cast<int>(s.size());
    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 inside = 0;
    for (int i = 0; i + 1 < n; ++i) inside = max(inside, pi[i]);
    int length = pi[n - 1];
    while (length > inside) length = pi[length - 1];
    if (length == 0) cout << "Just a legend\n";
    else cout << s.substr(0, length) << '\n';
}

时间 O(n)，额外空间 O(n)，包含输出在内仍为线性。输入保证非空，因此 pi[n−1] 有效。

边界 应发生什么
a 或 aa 没有严格内部的第三次出现
ababa aba 只有两端出现，答案退到 a
abcabc 不能把唯一末尾出现算成内部
一百万个 a 答案长度 n−2，不能逐候选重新扫描

第二题 432D 把每个结尾贡献给它的所有边界

现在不是找一个答案，而是输出所有既为前缀又为后缀的非空字符串，并给出它们在整串中的出现次数。整串本身也要输出，重叠出现照样计数，按长度递增输出。

枚举每条边界，再完整扫描一遍字符串，在 AAAAA… 上会变成平方级。另一种想法是枚举每个结束位置：它为哪些前缀贡献了一次出现？

将长度当作节点

让长度 k 的父节点为 pi[k−1]，k 的范围为 1 到 n，0 是空串根。父节点严格更小，形成一棵隐式的失败链接树，无需建立邻接表。

先令 cnt[k]=1，表示前缀 s[0..k−1] 在自己的结尾 k−1 处出现一次。然后按 k 从 n 到 1 倒序执行 cnt[pi[k−1]] += cnt[k]。

这一步统计的不只是原始前缀：一旦某个长前缀在其他位置结束，它的所有边界也在该位置结束，所以这次出现需要沿父链贡献给更短前缀。倒序确保子节点的完整计数先到达父节点。

正确性可以按结束位置理解：在位置 i 结束的所有前缀匹配，恰好是长度 i+1 节点及其祖先。节点 i+1 的那一份初始贡献会且只会经过这条祖先链，每个匹配计一次，没有遗漏或重复。

自造例子 s=ABABA 数值
pi 0，0，1，2，3
父链接 5→3→1→0；4→2→0
每个非空节点的初始 cnt 都是 1
5 汇入 3 后 cnt[3]=2
4 汇入 2 后 cnt[2]=2
3 汇入 1 后 cnt[1]=3
整串候选链 5，3，1；反转后输出
输出长度 对应字符串 出现起点从 0 开始 次数
1 A 0、2、4 3
3 ABA 0、2 2
5 ABABA 0 1

cnt[2] 也被正确计算为 2，但 AB 不是整串后缀，因此不能输出。统计全部前缀的频次与筛出整串边界是两项不同工作。

完整 C++17 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    cin >> s;
    int n = static_cast<int>(s.size());
    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;
    }
    vector<long long> cnt(n + 1, 1);
    cnt[0] = 0;
    for (int length = n; length >= 1; --length) {
        cnt[pi[length - 1]] += cnt[length];
    }
    vector<int> borders;
    for (int length = n; length > 0; length = pi[length - 1]) {
        borders.push_back(length);
    }
    reverse(borders.begin(), borders.end());
    cout << borders.size() << '\n';
    for (int length : borders) cout << length << ' ' << cnt[length] << '\n';
}

时间 O(n)，空间 O(n)。单个前缀的频次不超过 n，int 在本题约束下足够；这里用 long long 储存计数，便于后续扩展。不是把所有子串的总数量塞进同一个 cnt。

常见错误 为什么不对
从小到大传递 cnt 父节点已经处理完，后来收到的贡献无法继续上传
从 pi[n−1] 开始输出 漏掉长度 n 的整串
再给所有 cnt 加一次 1 本实现初始化时已计入自身，会重复统计
把所有 cnt 非零的长度都输出 它们不一定同时是整串后缀

第三题 471D 用差分消去整体平移

给定长度 n 的墙高 A 和长度 w 的模式 B，允许将 B 整体升高或降低，统计 A 中有多少个连续长度 w 的区间具有相同形状。整体偏移可以为负，不能要求两段首项相等。

若区间起点是 l，匹配的含义是存在常数 c，使每个位置都有 A[l+j]=B[j]+c。逐窗口逐元素尝试的朴素方法需要 O(nw)。

相邻差相等是充要条件

必要性很直接：相邻两式相减，常数 c 消失，因此 A[l+j+1]−A[l+j]=B[j+1]−B[j]。

充分性同样重要：若所有相邻差都相等，取 c=A[l]−B[0]。对 j 逐项累加相邻差，就得到 A[l+j]−B[j]=c。只要第一项确定偏移，其余位置都会一致。

于是长度 w 的高度匹配变成长度 w−1 的差分模式匹配。可以直接在整数数组上跑 KMP；算法只需要比较元素是否相等，不关心元素是不是字符。

对象 高度或相邻差
A 3，5，4，7，9，8
A 的相邻差 2，−1，3，2，−1
B 10，12，11
B 的相邻差 2，−1
合法高度窗口 3，5，4 与 7，9，8
相应偏移 c −7 与 −3

单列模式先单独处理

w=1 时差分模式为空，但不是“没有匹配”：任意单根柱子都能通过一个偏移匹配，答案为 n。代码先处理该情况，避免访问空模式。w>n 时没有完整窗口，答案为 0。

匹配到完整差分模式后，令 j=pi[j−1]，而不是强制归零。这样才能继续发现重叠匹配，例如所有高度相同、所有差分为 0 的情况。

完整 C++17 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, w;
    cin >> n >> w;
    vector<long long> a(n), b(w);
    for (auto &x : a) cin >> x;
    for (auto &x : b) cin >> x;
    if (w == 1) {
        cout << n << '\n';
        return 0;
    }
    if (w > n) {
        cout << 0 << '\n';
        return 0;
    }
    int m = w - 1;
    vector<long long> pattern(m);
    for (int i = 0; i < m; ++i) pattern[i] = b[i + 1] - b[i];
    vector<int> pi(m, 0);
    for (int i = 1; i < m; ++i) {
        int j = pi[i - 1];
        while (j > 0 && pattern[i] != pattern[j]) j = pi[j - 1];
        if (pattern[i] == pattern[j]) ++j;
        pi[i] = j;
    }
    long long answer = 0;
    int j = 0;
    for (int i = 1; i < n; ++i) {
        long long delta = a[i] - a[i - 1];
        while (j > 0 && delta != pattern[j]) j = pi[j - 1];
        if (delta == pattern[j]) ++j;
        if (j == m) {
            ++answer;
            j = pi[j - 1];
        }
    }
    cout << answer << '\n';
}

总时间 O(n+w)，这份实现保存两组输入，空间 O(n+w)；KMP 自身的额外状态为 O(w)。高度是正数，但差分可以为负，不能改用无符号整数。按本题范围，相邻差在 −999999999 到 999999999 之间；使用 long long 也可避免扩展高度范围时无意溢出。

三题共享什么又在哪分开

任务 pi 表示什么 额外操作 不能混淆的地方
126B 每段前缀的最长真边界 排除末位置，筛选内部出现 真边界允许重叠，但内部不能等于两端位置
432D 长度节点的父链接 倒序累加贡献，再输出整串边界 整串要输出，初始化方式决定是否另加 1
471D 差分模式的回退状态 扫描整数差分并计数 原模式长 w，差分模式长 w−1

把三题连起来，值得记住的不是一个变量名，而是三种复用方式：保留失配后仍成立的边界、把相同结束位置的贡献向上传递、先消掉不影响答案的自由度再做匹配。

用独立算法检查而不是再写一份 KMP

配套验证程序直接提取本文三份 C++17 编译执行。前两题的参考方法枚举长度、起点并逐字符比较；第三题在原高度上检查每个窗口的统一偏移，不先做差分。这样被测实现与参考实现不会共享失败链接或差分转换中的同一处错误。

tests/verify-string-matching-three-article.cjs 已以 C++17、优化和警告选项无警告编译三份代码。验证覆盖 697 组短字符串、902 组墙高测试及大规模字符串专项，总计 2,299 次程序执行、204,791 个结果值检查；其中包含一百万字符的 126B 输入、十万字符且输出全部边界的 432D 输入，以及二十万根柱子的 471D 输入。

测试方向 要抓出的错误
短二元字符串穷举 边界链不全、内部位置限制、重叠遗漏
随机多字母字符串 多次失配回退与无边界情况
随机高度和自造平移窗口 正负差分、全局平移、w 大于 n
全相同与交替高度 大量重叠匹配和失败链接复用
最大长度输入 平方算法、输出规模、下标边界

做完可回到算法练习路径，与树上 DFS 与子树汇总比较：432D 的失败链接虽然来自字符串，汇总方向却仍是“孩子的贡献先到父亲”。所有文章也收录在资源索引。