ABC441 E题解析：哈希+LCP判定子串字典序的存在性

这周的 ABC441 E 题光看名字“A B substring”就挺劝退很多人第一反应是“所有子串比较对吧那枚举都枚举不完”。实际上想通之后这题考的是一个非常典型的转化把“是否存在一对子串满足大小关系”换成“两个代表元素之间的大小关系”。这篇题解不重复第一版的双指针扫描思路专门补一个哈希 LCP 的通用判定写法方便拿去对拍也方便改造成多次询问的版本。先说清楚本篇以最常见版本为例给你两个整数序列 A 和 B长度分别为 n 和 m再给一个长度 K问是否存在 A 的一个长度为 K 的连续子串以及 B 的一个长度为 K 的连续子串使得前者的字典序严格大于后者。如果存在输出任意一对合法区间不存在则输出 No。下面所有讨论都基于这个版本。如果原题要求的是计数或者允许两个子串长度不同我在后面会指出改动方向。1. 题目拆解A B substring 到底在考什么1.1 题面常见形态固定长度 K 的判断问题ABC 系列的 E 题经常把问题包装成“序列”“substring”“字典序”的组合。这道题的核心其实是长度固定为 K 的两个子串怎么比较。很多同学一眼看上去会以为要枚举所有起点然后对于每组起点再逐位往后比较直觉复杂度是 O(n * m * K)n、m 到 2e5 就直接爆炸。但注意题目问的是“是否存在”不是“有多少个”。一旦问存在性往往就可以用代表元素来简化集合。长度为 K 的子串A 里面一共有 n - K 1 个B 里面一共有 m - K 1 个。我们要找的是一对满足“A 子串 B 子串”的组合。如果直接两两枚举哪怕 K 固定最坏也要 O(nm) 对还是过不了。1.2 暴力枚举为什么不可行很多人会想先枚举 A 的起点 i再枚举 B 的起点 j然后用前缀哈希 O(1) 求出两个子串的哈希相等就继续找第一个不同位。但即使比较两个子串是 O(log K)枚举所有起点对仍然是 O(nm log K)n、m 同时 2e5 时完全不现实。这时候需要跳出来看。既然只问存在性能不能不枚举“每一对”答案是能。关键结论是如果存在一对可行组合那么 A 集合中的字典序最大子串一定大于 B 集合中的字典序最小子串反过来如果 A 的最大子串大于 B 的最小子串那这两个子串本身就是一组可行解。这个结论成立的原因是字典序比较是全序关系具有传递性。设 A 最大子串为 maxAB 最小子串为 minB。如果存在某个 A 子串 a 大于某个 B 子串 b那么 maxA a b minB所以 maxA minB。反之如果 maxA minB那么 maxA 和 minB 就是我们要找的那一对。这样一来整个判定就转换成两个任务在 A 中找长度为 K 的最大子串在 B 中找长度为 K 的最小子串。1.3 字典序比较的本质第一个不同字符长度相同的两个子串比较大小第一个不同位置就决定了结果。比如 “123” 和 “120”前两位相同第三位 3 0所以前者更大。如果所有位都相同则两个子串相等。所以任意两个等长子串的比较最重要的是找到它们的最长公共前缀长度 LCP。有了 LCP问题就变成了如果 LCP K两个子串完全相等返回相等如果 LCP K比较第 LCP 位上的数字大小即可。这里为什么不直接逐位比较因为 K 可能很大逐位比较一个起点对是 O(K)不能接受。我们需要一种能在 O(log K) 甚至 O(1) 时间内求出 LCP 的手段。常用手段有两种字符串哈希二分或者后缀数组 RMQ。这篇题解先讲哈希版本代码量小容易理解和改造。2. 核心思路用“最大子串 最小孼串”一次判定2.1 集合代表元思想如果存在一对就一定存在“A最大”和“B最小”这个思想是整道题最精彩的地方。很多存在性题目的通用套路是找集合的极值代表然后只用极值判断。拿这题来说在 A 的所有长度 K 子串中找一个字典序最大的记为 maxA在 B 的所有长度 K 子串中找一个字典序最小的记为 minB判断 maxA 和 minB 的大小关系。如果 maxA minB说明 A 里最大的子串都压不过 B 里最小的子串那其他 A 子串更不可能大于 B 子串答案只能是 No。如果 maxA minB答案直接是 Yes并且 maxA 和 minB 对应的两个区间就是合法解。这个转化最大的收益是把二维枚举降成了一维扫描。找 maxA 需要扫一遍 A找 minB 需要扫一遍 B每次比较两个子串用哈希二分 O(log K)整体复杂度就是 O((n m) log K)完全可以接受。2.2 为什么不能用二分长度直接莽有人可能会想既然要判断是否存在一个长度 K也许可以对 K 做二分求“可行的最小长度”或者“最大长度”。这里必须提醒一下可行性关于长度并不单调。举个例子A [1, 9, 0]B [2, 8, 0]。长度 1 时A 最大值是 9B 最小值是 29 2可行。如果硬要造一个反例想说明长度 1 不可行、长度 2 可行需要让 A 的所有数字都小于等于 B 的所有数字但两个数字组合起来却可能大。比如 A [0, 9]B [1, 8]。长度 1 时 maxA 9minB 1依旧可行。所以 K1 是否可行取决于 maxA 和 minB 的关系。更直接的反例是可行性集合不一定连续。A [1, 9, 0]B [2, 8, 0]长度 1 可行长度 2 时 A 的子串是 19、90B 的子串是 28、8090 80 可行长度 3 时 A 全串 190B 全串 280190 280 不可行。你看可行长度集合是 {1, 2}不是从某个 K 开始一直成立。如果题面问的是“最小可行长度”直接二分会出问题。所以本篇只讨论固定 K 的判定版本这也是这类题目最常考的形式。2.3 算法复杂度预估先预处理两个数组的哈希O(n m)。然后 check(K) 需要扫一遍 A找最大 K 长子串每次比较 O(log K)总计 O(n log K)扫一遍 B找最小 K 长子串同样 O(m log K)最后比较 maxA 和 minBO(log K)。总复杂度 O((n m) log K)。空间上哈希数组 O(n m)。如果 n、m 都是 2e5这个复杂度非常稳实测不会跑满因为 K 的 log 最多也就 18 左右。3. 完整实现哈希 LCP 比较函数3.1 哈希预处理与 get哈希部分我用双模数减少碰撞风险。很多人习惯用 unsigned long long 自然溢出省事但在 OJ 上如果数据不刻意构造问题不大不过为了保险我建议至少用一个 1e9 级别的质数取模。下面代码里用两个模数代价很小收益是更稳。有一个细节数组元素范围可能是 0 到 9。如果直接用原数字作为哈希值那么子串 “00” 和子串 “0” 在长度不同时可能出现哈希歧义。虽然我们比较的是固定长度 K但把元素映射到 a[i] 1 可以在根源上避免前导零带来的额外风险。base 我取 911382323注意这个数要小于两个模数。哈希查询函数 get(l, r) 返回区间 [l, r] 的哈希对左闭右闭。代码里下标统一用 0-index方便和 vector 对应。#include bits/stdc.h using namespace std; using ll long long; const ll MOD1 1000000007LL; const ll MOD2 1000000009LL; const ll BASE 911382323LL; struct Hash { int n; vectorint s; vectorll h1, h2, p1, p2; Hash() {} Hash(const vectorint a) { n (int)a.size(); s.resize(n); for (int i 0; i n; i) { s[i] a[i] 1; } h1.assign(n 1, 0); h2.assign(n 1, 0); p1.assign(n 1, 1); p2.assign(n 1, 1); for (int i 0; i n; i) { h1[i 1] (h1[i] * BASE s[i]) % MOD1; h2[i 1] (h2[i] * BASE s[i]) % MOD2; p1[i 1] p1[i] * BASE % MOD1; p2[i 1] p2[i] * BASE % MOD2; } } pairll, ll get(int l, int r) const { if (l r) return {0, 0}; ll v1 (h1[r 1] - h1[l] * p1[r - l 1] % MOD1 MOD1) % MOD1; ll v2 (h2[r 1] - h2[l] * p2[r - l 1] % MOD2 MOD2) % MOD2; return {v1, v2}; } };这里 p1、p2 是 base 的幂次预处理到数组长度即可。get 里面的减法取模注意先乘再取模并且加上 MOD 防止负数。3.2 LCP 二分与子串比较函数有了 get求两个子串的最长公共前缀 LCP 就很简单二分长度 mid每次判断两个区间前 mid 个字符的哈希是否相等。如果相等说明公共前缀至少 mid继续往大试否则缩小。注意二分终点是 K 而不是无限大因为我们只需要在 K 长度内找第一个不同位置。代码中用左闭右开的思想lo 表示已知可行的 LCP 长度hi 是上界。mid 取 (lo hi 1) / 2 是为了正确处理边界。int lcp(const Hash HA, const Hash HB, int x, int y, int maxLen) { int lo 0, hi maxLen; while (lo hi) { int mid (lo hi 1) 1; if (HA.get(x, x mid - 1) HB.get(y, y mid - 1)) { lo mid; } else { hi mid - 1; } } return lo; } int cmpSub(const Hash HA, const vectorint VA, int x, const Hash HB, const vectorint VB, int y, int len) { int p lcp(HA, HB, x, y, len); if (p len) return 0; return VA[x p] VB[y p] ? -1 : 1; }cmpSub 返回 -1、0、1分别表示子串 V1 小于、等于、大于子串 V2。注意 p len 的情况代表两个子串完全相等这时必须返回 0不能因为某个字符悬空就乱判。这个函数是后面找最大值和最小值的唯一比较入口。3.3 check 函数与主流程代码check(K) 要做的事情很清晰如果 K 小于 1 或者大于 n、m 任意一个直接返回 false扫一遍 A维护最大子串起点 startA扫一遍 B维护最小子串起点 startB比较 A 的 startA 子串和 B 的 startB 子串返回是否大于。找最大值时比较两个 A 子串调用 cmpSub(HA, A, i, HA, A, startA, K)注意比较结果 0 说明当前 i 子串更大需要更新。找最小值时相反 0 说明当前 i 子串更小更新 startB。bool check(int K, const vectorint A, const vectorint B, const Hash HA, const Hash HB, int startA, int startB) { int n (int)A.size(); int m (int)B.size(); if (K 1 || K n || K m) return false; startA 0; for (int i 1; i K n; i) { if (cmpSub(HA, A, i, HA, A, startA, K) 0) { startA i; } } startB 0; for (int i 1; i K m; i) { if (cmpSub(HB, B, i, HB, B, startB, K) 0) { startB i; } } return cmpSub(HA, A, startA, HB, B, startB, K) 0; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m, K; cin n m K; vectorint A(n), B(m); for (int i 0; i n; i) cin A[i]; for (int i 0; i m; i) cin B[i]; Hash HA(A), HB(B); int startA -1, startB -1; if (check(K, A, B, HA, HB, startA, startB)) { cout Yes\n; cout startA 1 startA K \n; cout startB 1 startB K \n; } else { cout No\n; } return 0; }输出时注意转成 1-index。startA 1 到 startA K 就是 A 中的合法区间startB 同理。这个代码结构是可迁移的后面如果要改成多次询问只需要把 check 单独拿出来循环调用即可。4. 验证与避坑样例、边界和性能实测4.1 手工验证两个小样例先看一个可行样例。A [1, 5, 3]B [1, 2, 9]K 2。A 的长度 2 子串有 15、53最大是 53起点是下标 1。B 的长度 2 子串有 12、29最小是 12起点是下标 0。53 12所以输出 Yes区间分别是 [2, 3] 和 [1, 2]。肉眼检查A[2..3] “53”B[1..2] “12”确实满足。再看一个无解样例。A [1, 2, 3]B [4, 5, 6]K 1。A 的最大 1 长串是 3B 的最小 1 长串是 43 4 为假输出 No。这也符合直觉因为 A 里任何单个数字都小于 B 里任何单个数字。4.2 哈希题最容易踩的四个坑第一个坑是 base 等于字符集大小。如果元素是 0 到 9然后你选 base 10那子串 “01” 的哈希和子串 “1” 的哈希可能相同。我们虽然只比较固定长度但 lcp 二分过程中涉及不同长度的前缀区间所以尽量不要用过于简单的 base。推荐选一个大质数比如 131、13331或者代码里的 911382323。第二个坑是模数乘法溢出。有些同学习惯用 int 存哈希乘个 base 再加字符直接溢出变成负数。C 里 int 溢出是未定义行为建议用 long long 存并且在每一步取模。get 函数里 h1[l] * p1[...] 也要小心两个 1e9 级别的数相乘接近 1e18long long 能装下但最好先取模再乘避免不必要的风险。第三个坑是 lcp 二分边界写错。我见过很多人写 lcp 时用 while (l r)然后 mid (l r) / 2最后把 l 当成 LCP这样在“全部相等”时会少算一个。正确的模板应该是 lo 表示已知相等前缀长度hi 是上界mid (lo hi 1) / 2。如果判断相等lo mid否则 hi mid - 1。这样循环结束后 lo 就是 LCP 准确值。第四个坑是 cmp 返回值的符号写反。找 A 最大子串时当前子串大于候选才更新所以要判 cmp 0找 B 最小子串时当前子串小于候选才更新所以要判 cmp 0。我一开始写反过一次结果样例全过一跑随机数据就错最后对拍才发现是符号问题。4.3 进一步的优化路线后缀数组 RMQ如果题目数据继续加大或者询问次数很多哈希 二分的 O((n m) log K) 可能会有点紧。这时候可以考虑后缀数组 RMQ 的方式把比较两个子串的时间压到 O(1)。做法是构造一个新串 S A 分隔符 B求后缀数组和 height 数组然后用 ST 表维护 height 的区间最小值。任意两个后缀的 LCP 就是 height 数组上的区间最小值查询。有了 O(1) 的 LCPcmpSub 就变成 O(1)check(K) 整体降到 O(n m)。缺点是后缀数组和 ST 表代码量大不少如果只是比赛快速 AC哈希版本通常已经够了。对于频繁询问不同 K 的情况还可以讨论滑动窗口维护最大/最小子串但因为相邻两个长度为 K 的子串只差一个字符理论上可以用单调队列做字符串的比较。不过实现起来要小心不如后缀数组来得彻底。这里就不展开了思路留给读者自己验证。5. 写在最后的一点点经验5.1 对拍脚本的写法这道题特别适合写一个暴力程序对拍。暴力做法就是枚举 A 的每个起点 i再枚举 B 的每个起点 j用循环逐位比较长度 K 的子串。因为 K、n、m 在小数据范围内暴力跑得飞快。对拍时生成随机数组元素取 0 到 9长度取 1 到 8K 取 1 到 min(n, m)然后反复比较暴力结果和哈希 check 的结果。我实测随机生成几万组两边结果完全一致。特别是当元素全相同、或者全递增时最容易暴露比较函数的边界问题一定要把这些边界数据也加进去。5.2 这类题推广到其他序列比较问题这个“最大 最小”的代表元思想不只在 A B substring 这类题里有用。任何两个集合如果比较关系是全序的并且问题只要求存在性都可以想一想能不能用极值代表来化简。比如判断 A 序列是否存在某个区间和大于 B 序列某个区间和可以把问题转化成“A 的最大子段和”和“B 的最小子段和”的关系。当然具体能不能用要看题目限制和是否允许部分区间的长度不同。我个人实际写这题时先用暴力验证了代表元思想的正确性再写了哈希版本。哈希在竞赛里不是绝对严格所以对拍一定要做。如果你追求 100% 正确性就把比较部分换成后缀数组 RMQ。希望这篇补充分享能帮你把这类子串比较题彻底吃透。