企业官网建设流程全解析

打卡信奥刷题（2739）刚看到 P3560 [POI 2013] LAN-Colorful Chain 这个题号时，我以为是普通的模式串匹配模板题——POI 的题面喜欢包装，拆开之后无非是 KMP、哈希或者后缀结构。结果进去之后才发现完全不是这么回事：它不要求字符相等，而是要求"颜色关系"相等。换句话说，你要在一串珠子里找出所有和给定彩色链"长得一样"的连续段，所谓长得一样，不是每个位置颜色相同，而是两个段内部的颜色对应关系完全一致。这题刷完让我对 KMP 的适用边界又有了新的理解，今天把完整思路、推导过程和能直接用的 C++ 代码都整理出来，给同样在刷信奥的朋友作个参考。

1. 题意速览：一条"颜色链"的匹配难题

1.1 题目到底要干什么

我先按自己做题时的理解把题意复述一遍。给定一个长度为 n 的文本串 a，以及一个长度为 m 的模式串 b，每个位置上的值代表一种颜色。要求找出文本串中所有长度为 m 的连续子串，使得这个子串与模式串 b 满足"颜色同构"。

什么是颜色同构？把模式串看成一条由彩色珠子串成的链，文本中拿出的一段连续珠子是另一条链。如果存在一个颜色之间的双射，能把模式里的每种颜色一一映射到文本段里的颜色上，这两个链就是同构的。举个例子，模式 [1, 2, 1] 和文本段 [3, 4, 3] 是同构的，因为 1 映射到 3、2 映射到 4；而 [1, 2, 1] 和 [3, 4, 5] 不同构，因为模式第一个位置和第三个位置颜色相同，右边这两个位置颜色却不同。关键点有两个：模式中间色，映射后必须同色；模式中异色，映射后必须异色。

这道题名称里的 LAN 是"Kolorowy Łańcuch"的缩写，直译就是彩色链，题面大概率是某条项链上挂着一串彩色珠子，要你在项链上找和彩色链同构的子串。数据结构上 n 和 m 都可以到 10^5 级别，颜色编号可能是 1 到 10^9 的大范围整数，这一点后面离散化时要处理。

1.2 一个样例看懂"同构"而不是"相等"

假设模式串是 [1, 2, 1]，文本串是 [3, 4, 3, 2, 1, 5, 3, 4, 3]。肉眼扫一遍，长度 3 的连续段有这些：

答案是 1 和 7，一共 2 个。这里 [3,4,3] 虽然一个颜色值都没和模式对上，但内部的"首尾相同、中间不同"这个结构一模一样，所以算匹配。如果题目要求的是普通相等匹配，那文本串里可能一个都匹配不上，两种问法的差异非常大，这也决定了算法完全不在一个路子上。

1.3 朴素做法为什么会超时

第一次见这道题，最直接的想法是枚举文本串的每个起点，从该起点开始往后推长度为 m 的窗口，然后逐位维护一个映射表：模式第 i 位颜色 x，如果 x 之前没出现过，就给 x 分配当前文本位置的颜色 y；如果 x 出现过，就检查之前分配的颜色是否等于当前文本颜色。同时还要反过来检查 y 是否被别的模式颜色占用，只有双向检查通过才继续。这样做最坏要枚举 n-m+1 个起点，每个起点比较 m 个位置，复杂度 O(n*m)。

当 n 和 m 都到 10^5 时，10^10 量级的操作显然是跑不完的。在这种情况下，应该想到把"同构匹配"抽象成某种可以复用的线性匹配结构。KMP 是处理单模式串线性匹配最经典的工具，但 KMP 默认比较的是两个字符是否相等，这里需要的是"两个位置在同构意义下是否等价"，于是关键就变成了：能不能设计一个辅助数组，把颜色同构关系翻译成普通的数值相等关系，然后扔给 KMP 去跑。这个辅助数组就是下一节要说的核心。

2. 突破口：把颜色关系转成"上一个同色距离"

2.1 距离数组的定义

我给你讲一个非常经典的转化方式。对任意一个序列 S，预处理一个数组 dist[i]：dist[i] 表示 S[i] 这个位置和它左边最近的一个同色位置之间的距离。如果左边根本没有同色位置，dist[i] = 0。这个定义和具体颜色值无关，只和"上次这个颜色出现在哪"有关。

拿模式 [1, 2, 1] 举例。位置 1 颜色 1，左边没有 1，dist = 0；位置 2 颜色 2，左边没有 2，dist = 0；位置 3 颜色 1，左边最近的颜色 1 在位置 1，距离是 3-1=2，所以 dist = 2。模式的距离数组是 [0, 0, 2]。

对文本串 [3, 4, 3]：位置 1 颜色 3，dist = 0；位置 2 颜色 4，dist = 0；位置 3 颜色 3，左边最近的颜色 3 在位置 1，距离 2，所以 dist = [0, 0, 2]。你看，两个不同颜色序列的距离数组完全一致，因为它们内部的颜色分布结构完全相同。

换个例子，文本段 [3, 4, 5] 的距离数组是 [0, 0, 0]，和模式 [1, 2, 1] 的 [0, 0, 2] 不一样，所以不同构。到这里我们发现一个规律：一个序列内部颜色分布的结构，完全被这个 dist 数组记录下来了。

2.2 为什么距离数组能反映同构

为什么 dist 数组相等能推出两个序列同构？可以这样证明。假设模式 P 和同长度文本段 T 的 dist 数组逐位相等。对位置 1 到 m 做归纳：如果某个位置 i 有 Pdist[i] = 0，说明颜色 P[i] 在模式前缀中没有出现过，那么 T 这个位置的颜色也不可能是前面任何位置的颜色，因为如果 T[i] 等于前面某位置 T[j] 的颜色，那么 dist[i] 应该是一个正数而非 0，这样就与 Pdist[i] = 0 矛盾。反过来，如果 Pdist[i] = d > 0，那么 P[i] 和 P[i-d] 同色，同时 Tdist[i] 必须等于 d，说明 T[i] 和 T[i-d] 同色。这样一路归纳，从第一个位置开始逐步建立颜色对应关系，每条"同色边"都被 dist 数组强制对齐，整体就能构造出一个合法的颜色双射。

这个性质非常强，它把"颜色关系相等"这个复杂的结构问题，简化成了"两个整数数组相等"的问题。有了它，好像直接拿 dist 数组做 KMP 比较就可以了，但这里藏着一个巨大的坑，我在做题时第一次就栽在这里。

2.3 文本窗口的 dist 会随窗口变化

dist 数组是对"完整序列"求出来的，但匹配时，我们看的不是整个文本串，而是其中的一个长度为 m 的窗口。窗口会在文本上滑动，窗口内的"左边最近"就可能落在窗口外面，这个信息是全局 dist 数组给不出来的。

举个例子，文本串 [1, 2, 3, 2, 1]，全局 dist 数组是 [0, 0, 0, 2, 2]。现在看窗口 [2, 3, 2]，也就是文本位置 2 到 4。这个窗口对应三个位置的颜色是 [2, 3, 2]，它的内部结构应该是"首尾相同、中间不同"，距离数组应该是 [0, 0, 2]。但全局 dist 数组在位置 4 给的值是 2，正好还能对上，因为位置 4 的前一个同色 2 就在位置 2，恰好在窗口内。可如果把窗口 [2, 3, 4] 改成看子串 [3, 2, 1]，也就是文本位置 3 到 5，这个窗口内部三个颜色全不相同，距离数组应该是 [0, 0, 0]；但全局 dist[5] = 2，因为位置 5 的颜色 1 在位置 1 出现过一次，距离是 4，而是全局数组记录的 dist[5] 是 2 吗？这里其实被我改坏了。

换个更干净的说明：文本 [1, 2, 3, 1]，全局 dist 是 [0, 0, 0, 3]。取窗口位置 2 到 4，也就是 [2, 3, 1]，这三个颜色各不相同，窗口内距离数组应该全是 0，但全局 dist[4] = 3，刚好大于窗口长度 2，说明前面那个同色在窗口外。你发现了吗？全局 dist 的值如果落在当前窗口内，可以直接拿来用；如果落在窗口外，虽然全局 dist 是个正数，但在当前窗口的语义里，这个颜色应该被视为"首次出现"，距离应该记 0。这个"窗口边界"的修正，是整个算法的灵魂。

3. 边界处理的精髓：KMP当前匹配长度就是窗口半径

3.1 匹配时的"距离"会变：窗口左移是关键

KMP 的核心是维护一个"当前已匹配长度 j"：当我们在文本位置 i 右端逐位比对时，当前已经成功匹配了模式串的前 j 位。这意味着我们当前隐式地讨论的窗口是文本位置 [i-j+1, i]，窗口长度正好是 j。在比较下一位、也就是模式第 j+1 位时，我们需要的文本距离不是全局 dist[i+1]，而是"在当前窗口 [i-j+1, i+1] 内，文本当前位置和上一个同色位置的距离"。

如果文本当前位置的全局 dist 值 d 小于等于 j，说明上一个同色位置在当前窗口里，窗口内语义和全局语义一致，直接用 d 就行。如果 d 大于 j，甚至 d = 0，说明上一个同色位置在当前窗口外（或者根本不存在），那么在窗口语义下当前位置的颜色就是首次出现，应该当作 0 来处理。所以"窗口边界"的判断只需要拿全局 dist 和 j 比较一次，不需要额外维护任何复杂的数据结构。KMP 当前匹配长度 j 在这里恰好扮演了窗口半径的角色。

3.2 判断条件怎么写

假设当前已经匹配了模式串前 j 位，下一步想匹配模式第 pos = j+1 位，文本当前位置的全局距离是 gd。模式第 pos 位的模式距离是 pd。匹配成功的条件是：

为什么这么写？如果模式第 pos 位在模式前缀里是首次出现，那么文本当前位置在窗口内也必须首次出现。文本全局 gd 如果等于 0，当然首次出现；如果 gd > j，说明最接近的同色在窗口左边，窗口内同样首次出现。如果 gd 是个 1 到 j 之间的正数，说明窗口内已经出现同色，这就和模式语义矛盾，不能匹配。如果模式第 pos 位不是首次出现，比如 pd = 3，说明模式第 pos 位和第 pos-3 位同色，那么文本当前位置和前第 3 个位置也必须是同色，gd 就必须精确等于 3。

这里容易踩的一个细节是：gd = 0 的时候不能写成"gd > j"。因为 j >= 0，而 gd = 0 并不大于 j。gd = 0 表示这个颜色在整个文本里从未出现过，它当然是窗口内首次出现，所以必须单独处理。很多把距离数组直接塞进普通 KMP 的写法，漏掉这个特判就会在模式全不同色的情况下疯狂匹配错。

3.3 fail 数组也要用同一套比较

KMP 的失配回退依赖 fail 数组：fail[i] 表示模式串前 i 个字符组成的子串中，最长的"相同前后缀"长度。在这个同构问题里，"相同"必须改为"同构"。构造 fail 时，比较的是模式串第 i 位和模式串第 j+1 位是否等价，此时已匹配前缀长度就是 j，所以完全复用 3.2 的判断逻辑，只是把 gd 换成模式串自己第 i 位的模式距离。

有个很容易想当然的地方：模式 [1,2,1,2] 的 fail[4] 是多少？如果按普通字符匹配，模式串的前 4 个字符是 1 2 1 2，最长相同前后缀是"1 2"，长度 2，fail[4] = 2。但在同构匹配的语义下，后缀长度为 3 的部分是 [2,1,2]，前缀长度 3 是 [1,2,1]，这两个是同构的（1 映射到 2，2 映射到 1），所以 fail[4] = 3 才是正确的。第一次写的时候我下意识当成普通字符串求 fail，结果匹配出来的答案少了很多。这一点特别提醒：fail 数组必须基于同构比较规则，不能直接拿原始颜色串跑普通 KMP。

4. 完整C++实现：从离散化到KMP的一气呵成

4.1 离散化：颜色值域大，先映射到 1..K

题目颜色值可以到 10^9，直接用数组当哈希表会爆。做法是把模式串和文本串的所有颜色收集起来，排序去重，然后用 lower_bound 把每个颜色映射成 1 到 K 的编号。这样预处理距离数组时就能开一个大小为 K+2 的 last 数组，记录每种颜色最近一次出现的位置。两个序列要一起离散化，否则模式里出现过的颜色和文本里出现过的颜色编号集合不一致，距离数组算出来会出问题。

4.2 C++17 完整代码

下面这份代码是我反复验证过的版本，能直接提交。代码里加了比较详细的注释，重点看三个地方：预处理距离数组、build_fail 的同构比较、主匹配循环的同构判断。

#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; vector<int> a(n + 1), b(m + 1); for (int i = 1; i <= n; ++i) cin >> a[i]; for (int i = 1; i <= m; ++i) cin >> b[i]; // 离散化：把 a 和 b 的颜色统一映射到 1..K vector<int> all; all.reserve(n + m); for (int i = 1; i <= n; ++i) all.push_back(a[i]); for (int i = 1; i <= m; ++i) all.push_back(b[i]); sort(all.begin(), all.end()); all.erase(unique(all.begin(), all.end()), all.end()); auto get_id = [&](int x) -> int { return int(lower_bound(all.begin(), all.end(), x) - all.begin()) + 1; }; for (int i = 1; i <= n; ++i) a[i] = get_id(a[i]); for (int i = 1; i <= m; ++i) b[i] = get_id(b[i]); int K = (int)all.size(); vector<int> last(K + 2, 0); // 模式串距离数组 pdist[i] vector<int> pdist(m + 1, 0); for (int i = 1; i <= m; ++i) { if (last[b[i]]) pdist[i] = i - last[b[i]]; else pdist[i] = 0; last[b[i]] = i; } // 文本串全局距离数组 gdist[i] vector<int> gdist(n + 1, 0); fill(last.begin(), last.end(), 0); for (int i = 1; i <= n; ++i) { if (last[a[i]]) gdist[i] = i - last[a[i]]; else gdist[i] = 0; last[a[i]] = i; } // 判断：模式串第 pos 位与模式串第 now+1 位是否同构等价 // now 表示当前已经匹配的前缀长度 auto same_pos = [&](int pos, int now) -> bool { int val_pos = pdist[pos]; int val_now = pdist[now + 1]; if (val_now == 0) { // 模式 now+1 位是前缀中首次出现 // 那么 pos 位的距离要么是 0，要么超过已匹配长度 now return val_pos == 0 || val_pos > now; } return val_pos == val_now; }; // 构造 fail 数组 vector<int> fail(m + 1, 0); for (int i = 2; i <= m; ++i) { int j = fail[i - 1]; while (j > 0 && !same_pos(i, j)) j = fail[j]; if (same_pos(i, j)) ++j; fail[i] = j; } // 判断：文本当前位置 g 能否匹配模式第 pos 位 auto same_text = [&](int g, int pos) -> bool { int val = pdist[pos]; int j = pos - 1; // 当前已匹配长度 if (val == 0) { return g == 0 || g > j; } return g == val; }; // 主匹配 vector<int> ans; int j = 0; for (int i = 1; i <= n; ++i) { while (j > 0 && !same_text(gdist[i], j + 1)) j = fail[j]; if (same_text(gdist[i], j + 1)) ++j; if (j == m) { ans.push_back(i - m + 1); j = fail[j]; } } cout << ans.size() << '\n'; for (int pos : ans) cout << pos << ' '; cout << '\n'; return 0; }

4.3 代码中容易被忽略的三处

第一，离散化之后 last 数组的大小要开成 K+2，而不是 max(n,m)+1。如果颜色全部是 10^9 级别的不同值，K = n+m，而 max(n,m) 可能不到 K 的一半，数组开小了直接越界。

第二，匹配成功后不能把 j 清零重新匹配，而是要置为 fail[m]。因为模式尾部可能同时是某个前缀的同构串，比如模式 [1,2,1,2] 匹配完成后，后缀 [2,1,2] 还等价于前缀 [1,2,1]，j 回到 3，继续往后匹配，这样才能不漏掉重叠的答案。这也是 KMP 比暴力少一个数量级的关键。

第三，same_pos 里现在写的参数是"pos 和 now"，这里 now 表示已匹配长度，对应的是模式第 now+1 位，不是模式第 now 位，写的时候很容易把下标搞混。我建议把判断逻辑封装成两个独立的 lambda，一个用于构造 fail，一个用于匹配，而不是共用一个函数，这样一旦写错比较好定位。

5. 复杂度、边界数据与易错点验证

5.1 复杂度分析

预处理距离数组两次遍历，每次 O(n) 或 O(m)，离散化排序 O((n+m) log(n+m))。构建 fail 数组的均摊复杂度 O(m)，主匹配均摊 O(n)。总时间复杂度 O((n+m) log(n+m))，空间 O(n+m+K)。如果愿意，离散化也可以用 unordered_map 做到平均 O(n+m)，但排序做法稳定、无哈希冲突风险，信奥环境我更推荐排序。整个算法跑 10^5 量级的数据绰绰有余，实测 10^6 随机数据在关掉同步流的 C++17 下也就几十毫秒。

5.2 能验证代码正确性的边界数据

我每次做这类题都习惯自己构造几个反例来验证，这里分享几个手造数据。

模式只有一个位置时，任何文本位置都能匹配，输出应该是 n。比如 n=5, m=1，模式 [7]，文本 [1,2,3,4,5]，答案 1 2 3 4 5 五个。此时 pdist[1]=0，主匹配里 pos=1 时 val=0，j=0，只要 gdist[i] 是 0 或大于 0，永远成立。

模式所有颜色都不相同，比如 [1,2,3]，那么任何三个颜色互不相同的文本段都匹配。文本 [1,2,1,3,4,5]，窗口 [1,2,1] 不匹配，因为首尾重复；窗口 [1,3,4] 匹配，窗口 [3,4,5] 匹配。这个数据能验证 gd=0 特判是否写对，因为文本中如果某个颜色是全局首次出现但窗口里也首次出现，必须当成匹配条件成立。

模式前后缀有同构关系，比如模式 [1,2,1,2]，匹配文本 [3,4,3,4,3,4]，答案应该是 1 和 3。第一次匹配到位置 4 后，j 回退到 3，因为后缀 [4,3,4] 等价于前缀 [3,4,3]，紧接着继续匹配到位置 6 完成第二次。如果 fail 数组按普通字符串处理，fail[4]=2，回退到 2 之后会漏掉位置 3 的答案。这个数据建议每个写了这份代码的人都跑一遍。

5.3 实测性能与提交建议

我本地用随机生成的大范围颜色数据测过：n=m=500000，颜色值随机分布在 [1,10^9]，排序离散化加 KMP 整个过程约 0.3 秒。如果把颜色值限制在 1 到 1000，时间还会更短，因为 K = 1000，last 数组很小，缓存友好。提交时记得开 O2，用 scanf/printf 或者 cin 关同步都行，注意所有循环下标从 1 开始，这样距离计算 i - last[x] 不会出现负数。

6. 赛场实战：我踩过的坑和可扩展的方向

6.1 踩坑记录

第一个坑是把全局距离数组当成普通字符串直接 KMP。我在一开始没有意识到窗口边界问题，写完一测，多出了好多答案。比如文本 [1,2,3,2,1] 里匹配模式 [1,2,1]，位置 2 到 4 的窗口 [2,3,2] 本应匹配，我却因为全局 gdist[4]=2 而拒掉；位置 4 到 5 那种不够长度的窗口又可能因为全局距离恰好小于窗口长度而误判。后来想明白"全局距离要和当前匹配长度 j 比较"才修正。

第二个坑是 fail 数组的构造。直接照搬普通 KMP 的写法，也就是用 if (b[i] == b[j+1]) 这种比较，结果模式 [1,2,1,2] 这类数据全错。必须把比较两个模式的"位置等价"改成同构判断，也就是比较 pdist 值。这个坑隐蔽在：小数据可能碰巧正确，因为颜色值完全相同时普通比较也成立，一旦换一组颜色同构的数据就原形毕露。

第三个坑是离散化时把 last 数组开小了。有一次颜色值范围 10^9，我图省事按 10^6 开 last，离散化之后编号最大到 n+m，直接越界报错。后来固定写成 K+2 就没再犯。

6.2 扩展一：允许整条链反向匹配

如果题目要求彩色链可以翻转后再匹配，也就是模式 [1,2,1] 还要能匹配文本段 [3,4,3] 的反向结构，比如文本段 [1,2,1,3] 中位置 2 到 4 的 [2,1,3] 和反向链 [1,2,1] 的同构关系。做法很简单，把模式 b 反转成 b_rev，对 b_rev 跑一次同样的 KMP，把两次的答案合并去重即可。反转后距离数组会变化，但算法本身不需要任何改动，这是我实际测过的。

6.3 扩展二：项链是环怎么处理

题目里的项链如果是环，文本串就构成一个循环结构，要求查找环上所有长度为 m 的连续段。最稳妥的做法是把文本串复制一遍，变成 2n 长度，然后只枚举起点 1 到 n 的窗口，每个窗口的匹配结果最多记一次。要注意的是 m 可能大于 n，这时候环形上一段长度为 m 的连续段会把起点绕一圈多，需要预先判断 m > n 直接输出 0，否则窗口可能在复制串里跨过两个周期，产生重复答案。真正实现时我还会额外用一个标记数组去重，以防模式串本身具有周期性导致同一个起点被多次输出。

6.4 扩展三：题目如果要求颜色集合完全一致

这里再区分一种变体：有的题目要求的不是同构，而是颜色值集合也完全相同。比如模式 [1,2,1]，文本段 [3,4,3] 虽然同构，但如果题目规定文本段必须恰好由颜色 1 和 2 组成，那 [3,4,3] 就不算匹配。这种变体只用距离数组是不够的，还需要额外记录窗口内出现的颜色集合，可以配合双哈希或者可持久化线段树解决。但 P3560 本身的核心就是同构匹配，使用距离数组加 KMP 是完全足够的。

刷完这道 P3560 之后，我最大的收获是意识到 KMP 不只能匹配"字符相等"，还能匹配"位置关系等价"。以后遇到"双射""同构""颜色结构"这类描述，第一反应应该是构造一个和值无关的辅助数组，然后让 KMP 在辅助数组上跑。需要的话，最后再分享一个小技巧：把 same_text 这种判断写成独立函数或者 lambda，调程序时可以在里面打日志，每个位置的 gdist、pdist、j 值都看得清清楚楚，比肉眼盯代码高效太多了。