P3560用距离数组+KMP解决颜色同构匹配问题

打卡信奥刷题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,2,1] 的关系1[3,4,3]同构1→32→42[4,3,2]不同构三个颜色互不相同模式末尾两个相同3[3,2,1]不同构三个颜色互不相同4[2,1,5]不同构5[1,5,3]不同构6[5,3,4]不同构7[3,4,3]同构1→32→4答案是 1 和 7一共 2 个。这里 [3,4,3] 虽然一个颜色值都没和模式对上但内部的首尾相同、中间不同这个结构一模一样所以算匹配。如果题目要求的是普通相等匹配那文本串里可能一个都匹配不上两种问法的差异非常大这也决定了算法完全不在一个路子上。1.3 朴素做法为什么会超时第一次见这道题最直接的想法是枚举文本串的每个起点从该起点开始往后推长度为 m 的窗口然后逐位维护一个映射表模式第 i 位颜色 x如果 x 之前没出现过就给 x 分配当前文本位置的颜色 y如果 x 出现过就检查之前分配的颜色是否等于当前文本颜色。同时还要反过来检查 y 是否被别的模式颜色占用只有双向检查通过才继续。这样做最坏要枚举 n-m1 个起点每个起点比较 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左边没有 1dist 0位置 2 颜色 2左边没有 2dist 0位置 3 颜色 1左边最近的颜色 1 在位置 1距离是 3-12所以 dist 2。模式的距离数组是 [0, 0, 2]。对文本串 [3, 4, 3]位置 1 颜色 3dist 0位置 2 颜色 4dist 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-j1, i]窗口长度正好是 j。在比较下一位、也就是模式第 j1 位时我们需要的文本距离不是全局 dist[i1]而是在当前窗口 [i-j1, i1] 内文本当前位置和上一个同色位置的距离。如果文本当前位置的全局 dist 值 d 小于等于 j说明上一个同色位置在当前窗口里窗口内语义和全局语义一致直接用 d 就行。如果 d 大于 j甚至 d 0说明上一个同色位置在当前窗口外或者根本不存在那么在窗口语义下当前位置的颜色就是首次出现应该当作 0 来处理。所以窗口边界的判断只需要拿全局 dist 和 j 比较一次不需要额外维护任何复杂的数据结构。KMP 当前匹配长度 j 在这里恰好扮演了窗口半径的角色。3.2 判断条件怎么写假设当前已经匹配了模式串前 j 位下一步想匹配模式第 pos j1 位文本当前位置的全局距离是 gd。模式第 pos 位的模式距离是 pd。匹配成功的条件是模式第 pos 位的距离 pd文本需要满足的条件pd 0gd 0 或 gd jpd 0gd 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 位和模式串第 j1 位是否等价此时已匹配前缀长度就是 j所以完全复用 3.2 的判断逻辑只是把 gd 换成模式串自己第 i 位的模式距离。有个很容易想当然的地方模式 [1,2,1,2] 的 fail[4] 是多少如果按普通字符匹配模式串的前 4 个字符是 1 2 1 2最长相同前后缀是1 2长度 2fail[4] 2。但在同构匹配的语义下后缀长度为 3 的部分是 [2,1,2]前缀长度 3 是 [1,2,1]这两个是同构的1 映射到 22 映射到 1所以 fail[4] 3 才是正确的。第一次写的时候我下意识当成普通字符串求 fail结果匹配出来的答案少了很多。这一点特别提醒fail 数组必须基于同构比较规则不能直接拿原始颜色串跑普通 KMP。4. 完整C实现从离散化到KMP的一气呵成4.1 离散化颜色值域大先映射到 1..K题目颜色值可以到 10^9直接用数组当哈希表会爆。做法是把模式串和文本串的所有颜色收集起来排序去重然后用 lower_bound 把每个颜色映射成 1 到 K 的编号。这样预处理距离数组时就能开一个大小为 K2 的 last 数组记录每种颜色最近一次出现的位置。两个序列要一起离散化否则模式里出现过的颜色和文本里出现过的颜色编号集合不一致距离数组算出来会出问题。4.2 C17 完整代码下面这份代码是我反复验证过的版本能直接提交。代码里加了比较详细的注释重点看三个地方预处理距离数组、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; vectorint 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 vectorint 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(); vectorint last(K 2, 0); // 模式串距离数组 pdist[i] vectorint 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] vectorint 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 位与模式串第 now1 位是否同构等价 // now 表示当前已经匹配的前缀长度 auto same_pos [](int pos, int now) - bool { int val_pos pdist[pos]; int val_now pdist[now 1]; if (val_now 0) { // 模式 now1 位是前缀中首次出现 // 那么 pos 位的距离要么是 0要么超过已匹配长度 now return val_pos 0 || val_pos now; } return val_pos val_now; }; // 构造 fail 数组 vectorint 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; }; // 主匹配 vectorint 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 数组的大小要开成 K2而不是 max(n,m)1。如果颜色全部是 10^9 级别的不同值K nm而 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 表示已匹配长度对应的是模式第 now1 位不是模式第 now 位写的时候很容易把下标搞混。我建议把判断逻辑封装成两个独立的 lambda一个用于构造 fail一个用于匹配而不是共用一个函数这样一旦写错比较好定位。5. 复杂度、边界数据与易错点验证5.1 复杂度分析预处理距离数组两次遍历每次 O(n) 或 O(m)离散化排序 O((nm) log(nm))。构建 fail 数组的均摊复杂度 O(m)主匹配均摊 O(n)。总时间复杂度 O((nm) log(nm))空间 O(nmK)。如果愿意离散化也可以用 unordered_map 做到平均 O(nm)但排序做法稳定、无哈希冲突风险信奥环境我更推荐排序。整个算法跑 10^5 量级的数据绰绰有余实测 10^6 随机数据在关掉同步流的 C17 下也就几十毫秒。5.2 能验证代码正确性的边界数据我每次做这类题都习惯自己构造几个反例来验证这里分享几个手造数据。模式只有一个位置时任何文本位置都能匹配输出应该是 n。比如 n5, m1模式 [7]文本 [1,2,3,4,5]答案 1 2 3 4 5 五个。此时 pdist[1]0主匹配里 pos1 时 val0j0只要 gdist[i] 是 0 或大于 0永远成立。模式所有颜色都不相同比如 [1,2,3]那么任何三个颜色互不相同的文本段都匹配。文本 [1,2,1,3,4,5]窗口 [1,2,1] 不匹配因为首尾重复窗口 [1,3,4] 匹配窗口 [3,4,5] 匹配。这个数据能验证 gd0 特判是否写对因为文本中如果某个颜色是全局首次出现但窗口里也首次出现必须当成匹配条件成立。模式前后缀有同构关系比如模式 [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 实测性能与提交建议我本地用随机生成的大范围颜色数据测过nm500000颜色值随机分布在 [1,10^9]排序离散化加 KMP 整个过程约 0.3 秒。如果把颜色值限制在 1 到 1000时间还会更短因为 K 1000last 数组很小缓存友好。提交时记得开 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[j1]) 这种比较结果模式 [1,2,1,2] 这类数据全错。必须把比较两个模式的位置等价改成同构判断也就是比较 pdist 值。这个坑隐蔽在小数据可能碰巧正确因为颜色值完全相同时普通比较也成立一旦换一组颜色同构的数据就原形毕露。第三个坑是离散化时把 last 数组开小了。有一次颜色值范围 10^9我图省事按 10^6 开 last离散化之后编号最大到 nm直接越界报错。后来固定写成 K2 就没再犯。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 值都看得清清楚楚比肉眼盯代码高效太多了。