双端取数构造字典序最小序列：从贪心反例到哈希与后缀数组优化

前阵子复盘这届校赛的 I 题题名就叫《字典序》题目备注里写了“双向指向 优化技巧”。这几个词放在一起我第一反应就是经典的“每次从左右两端取一个数构造字典序最小的序列”模型。这个模型看起来简单实际写起来坑不少一眼贪心是错的朴素比较是 O(n²)要稳稳通过大数据必须把“比较两个方向的字典序”优化到 O(log n) 甚至 O(1)。这篇文章就把这个模型的决策规则、两种优化方案、完整代码和踩坑记录从头到尾捋一遍适合刚入门算法竞赛、正在刷贪心和字符串哈希题的同学参考。1. 题目还原从“双向指向”猜出题的原型1.1 关键词拆解双向指向到底指什么“双向指向”本身不是某个固定算法名词它更像是对题目形态的描述。结合“字典序”这个核心目标最常见的模型就是给定一个长度为 n 的字符串也可以推广成整数序列每次只能从当前剩余串的最左端或者最右端取出一个字符放到答案序列的末尾问经过 n 次操作后能得到的字典序最小的答案是什么。这个模型里两个指针 l 和 r 分别指向当前剩余区间的左端和右端每次操作只能选择其中一个方向“前进”取左端就 l取右端就 r--。整个过程像两根指针不断从两头往中间扫算得上真正的“双向指向”。我复盘时先确认的就是这一点如果题目副标题里出现“双向指向”十有八九是这种双端取数模型而不是单纯的排序或者全排列枚举。为什么因为只有双端取数才会出现“当前选择会影响后续所有选择”的决策问题也才需要在两个指针之间反复做字典序比较。1.2 模型落地操作规则和结果形式假设当前剩余区间是 s[l..r]答案串是 ans。每次操作实际是在做一件事从 s[l] 和 s[r] 中挑一个字符拼到 ans 末尾然后移动对应的指针。最终 ans 的长度一定等于原串长度 n只是字符顺序被重新排列了。举个例子s ACDBCB一种操作顺序可以是取左端 A得到 ans A取右端 B得到 ans AB取右端 C得到 ans ABC取右端 C得到 ans ABCC取右端 B得到 ans ABCCB取左端 D得到 ans ABCCBD这个顺序显然不是最优的因为答案前三位 AB C 之后出现了两个 C而实际上完全可以构造出 ABCBCD 这种更紧凑的结果。所以问题的本质是每一步都要决定从哪一端取才能保证最后拼出来的 ans 字典序最小。这其实是一个在线决策问题每一步的选择都会锁死后续的可选区间不能反悔。1.3 这种题型的通用场景和变体双端取数构造字典序的问题在校赛、省赛里非常常见它可以包装成字符串、数字排列、甚至卡片游戏。我能想到的常见变体有原始数据是字符串答案也是字符串字符集为小写字母原始数据是 1 到 n 的排列要求输出的答案序列字典序最小题目要求字典序最大只需要把所有比较符号反过来限制每次必须连续取 k 个才切换方向这种会在决策规则上增加一层复杂度。无论哪种变体核心都是“如何高效比较两个方向的剩余区间”。这也是《字典序》这道题会被单独标注“优化技巧”的原因如果把比较做成朴素逐位扫描数据量稍微大一点就会超时。2. 你以为的贪心只看两端就够了吗2.1 一个反例推翻“直接取小”很多新手看到这个题的第一反应是每次都取两端中较小的字符不就行了如果 s[l] s[r] 取左边如果 s[l] s[r] 取右边两个相等就随便取。这个直觉在两端字符不同的情况下是对的但遇到两端相等时就会翻车。看这个例子s BCAB。两端都是 B如果直接取左端继续比较剩下 CAB两端是 C 和 B取 B答案前两位是 BB。如果第一步取右端 B剩下 BCA两端是 B 和 A取 A答案前两位是 BA。BB 和 BA 相比BA 明显更小。问题就出在两端字符相等时不能只看当前这一个字符必须看到后续的分叉点。经典样例 ACDBCB 里也有同样的陷阱中间出现两端都是 C 的情况如果直接取左端就会得到错误的答案。为什么会这样因为字典序的规则是“先比较第一个不同字符”。当 s[l] s[r] 时这一步无论取左还是取右答案都会加入同一个字符真正的胜负取决于剩下的区间分别能构造出什么。所以只看当前字符的贪心不是最优的它缺少向后看的能力。2.2 正确规则比较剩余串和它的反串经过上面的分析正确的决策规则其实可以统一成一句话每次比较当前剩余区间 s[l..r] 和它的反向串即从右往左读如果正向读的字典序更小就取左端否则取右端。这个规则可以覆盖所有情况当 s[l] s[r] 时正向串的第一个字符小于反向串的第一个字符正向一定更小取左端当 s[l] s[r] 时反向串更小取右端当 s[l] s[r] 时继续比较第二个、第三个字符直到找到第一个不同的位置再决定取哪边。用这个规则去跑 ACDBCB当剩余区间是 CDBC 时正向读是 C D B C反向读是 C B D C。第二个字符 D 大于 B所以反向更小这一步取右端。这样得到的答案就是 ABCBCD正确。为什么要用整个剩余区间和反串比较而不是用更复杂的递归这个问题的本质是剩下区间的“最优构造结果”和“顺着读/倒着读”的字典序有直接对应关系。如果正向串已经比反向串小说明从左边开始逐层决策的轨迹整体优于从右边开始由于每一步决策都可以递归地应用同一规则贪心选择“正反串中更小的一方”就是全局最优。2.3 朴素实现与复杂度为何会炸朴素做法很直观每个状态都写一个循环逐位比较 s[l..r] 和它的反向。伪代码大致是这样while l r: if s[l..r] reverse(s[l..r]): ans s[l], l else: ans s[r], r--问题在于 reverse(s[l..r]) 不能每次都真的构造出来否则单次比较就是 O(n) 的。即便只是写一个双层循环逐位比较最坏情况下每一步比较都可能扫描接近整个剩余区间总复杂度 O(n²)。当 n ≤ 2000 时O(n²) 可以轻松跑过但 n 到 1e5 甚至 5e5 时n² 就是 1e10 量级的操作显然超时。所以必须找到一种方法能快速回答“两个字符串片段谁字典序更小”这个子问题。这就是下面两种优化技巧的用武之地。3. 优化技巧一哈希 二分把比较降成对数级3.1 哈希如何支持“字典序比较”哈希优化字典序比较的核心思想是用二分查找找到两个串的第一个不同字符位置然后直接比较那个字符的大小。如果两个串在某个前缀完全相同那么它们的哈希值也一定相同。反过来如果哈希值不同说明第一个不同字符一定在这个前缀范围内。借助这个性质我们可以反复折半缩小范围找到最长公共前缀 LCP 的长度最后 O(1) 比较第一个不同的字符。整个过程就像查字典先翻到中间如果前半本内容完全一致就把范围缩小到后半本如果不一致就在前半本继续二分。每次比较两个区间的哈希值只需要 O(1) 时间所以单次“判断两个子串谁更小”的复杂度降到了 O(log n)。不过要注意单个哈希值可能碰撞比赛中常用双哈希来降低碰撞概率也就是同时用两个不同的模数和 base两个值都相等才认为两个区间相等。下面我给的代码就是双哈希版本。3.2 双哈希预处理参数与公式双哈希需要预处理好几个数组base 的幂次、原串的正向哈希、反串的正向哈希。我这里选用两个模数MOD1 1000000007MOD2 1000000009base 分别取 131 和 13331。实际使用中这两个组合在竞赛数据下足够稳。预处理公式很简单假设字符下标从 1 开始对于任意字符串 str定义h1[i] (h1[i-1] * base1 str[i-1]) % MOD1 h2[i] (h2[i-1] * base2 str[i-1]) % MOD2查询区间 [l, r] 的哈希值时用前缀和做差hash1(l, r) (h1[r] - h1[l-1] * pow1[r-l1] % MOD1 MOD1) % MOD1这里 pow1[k] 表示 base1 的 k 次方对 MOD1 取模。乘上 pow1[r-l1] 是为了对齐位数原理和十进制数字串的区间查询完全一样高位权重不能丢否则 “AB” 和 “B” 这样的串会被错误判断成等价。预处理原串和反串两份前缀哈希是为了在比较时快速查询“当前剩余区间”和“它的反向区间”。反向区间在反串中的位置需要做一次下标映射原串位置 l 对应反串位置 n - l 1所以原区间 [l, r] 的反向区间在反串中是 [n - r 1, n - l 1]。3.3 二分求 LCP 的比较函数写法有了哈希查询比较两个子串的字典序可以这样写先取两个串长度的最小值 len在 [0, len] 范围内二分最大 LCP 长度 mid如果 [l1, l1mid-1] 和 [l2, l2mid-1] 的哈希值相同说明前缀匹配缩短区间重新查二分结束后如果 LCP 到达 len说明两个串的公共前缀覆盖了较短串的全部内容此时较短串更小否则比较 s[l1 lcp] 和 s[l2 lcp] 这两个字符的大小即可。这里有个容易写错的细节二分的初始 hi 是 len而不是 len - 1。因为 LCP 最大可以等于整个较短串的长度这时两个串相等长度也相等的话需要返回“取左”的结果。mid (lo hi 1) 1 这种写法可以保证不会死循环。另外做哈希查询时减法的结果要加模数再取模防止负数。这一行虽然不起眼但在字符集较大或者前缀相乘溢出时最容易出 bug。4. 优化技巧二后缀数组让单次比较变成 O(1)4.1 后缀数组没法直接派上用场先澄清一个误区哈希加二分的总复杂度是 O(n log n)对 1e5 到 2e5 的数据完全够用。但如果 n 到 1e6每步多一个 log 还是有点肉疼。这时候可以引入后缀数组把单次比较优化到 O(1)。很多初学者有一个错误印象后缀数组的 rank 数组不就是字典序排名吗比较两个子串直接比 rank 不就行了没那么简单。rank 是对整个后缀进行排序的而我们要比较的子串只是后缀的一个前缀。两个子串如果前半段完全相同但其中一个后缀接下来有一个很小的字符那么这两个后缀的 rank 会差别很大可是子串本身可能仍然相等。所以不能直接拿 rank 当子串字典序必须借助 LCP 信息。正确做法是用后缀数组求出 height 数组再用 RMQ 预处理 height 区间最小值这样就能 O(1) 查询任意两个位置后缀的 LCP。有了 LCP比较两个子串的逻辑和哈希二分版的逻辑完全一样只是把“二分求 LCP”换成了“RMQ 直接取”。4.2 拼接反串 height RMQ 的正确姿势为了能同时查询原串两个任意区间的 LCP需要把原串和反串拼在一起T s # reverse(s)中间加一个分隔符是为了防止原串后缀和反串后缀跨过边界发生匹配。分隔符要选择原串中不可能出现的字符这样构建后缀数组时不会产生错误的后缀关系。接下来对 T 求 sa、rank 和 heightheight[i] 表示 sa[i] 和 sa[i-1] 对应后缀的最长公共前缀长度任意两个位置 pos1 和 pos2 的后缀 LCP等于它们在后缀数组中之间的 height 最小值这个区间最小值用 ST 表倍增表预处理之后每次查询 O(1)。当我要比较原区间 [l, r] 和反向区间 [rl, rr] 时先计算两个区间在 T 中的起始位置然后查这两个后缀的 LCP如果 LCP 大于等于区间长度说明两个区间完全相同否则比较第一个不同字符的大小。因为每个决策只需要一次 O(1) 的 LCP 查询整个求解过程的决策部分就是 O(n) 的。合成复杂度主要取决于后缀数组的构建复杂度一般是 O(n log n)如果使用线性构建算法可以到 O(n)。4.3 两种优化路线怎么选我平时做题会按数据范围来选方案方案单次比较复杂度总复杂度代码量适用数据范围朴素逐位比较O(n)O(n²)极少n ≤ 2000哈希 二分O(log n)O(n log n)较少n ≤ 5e5后缀数组 RMQO(1)O(n log n) / O(n)较多n ≤ 1e6 及以上哈希加二分的优点是代码短、思路直白适合在考场上快速实现。后缀数组方案虽然单次查询更快但构建过程本身就要写不少代码而且 ST 表也要额外空间性价比要综合评估。如果题目没有明确要求极限性能我推荐先用哈希二分跑一遍样例和大数据确认时间还有富余再决定要不要优化。毕竟赛后复盘和现场比赛不一样现场更多考虑的是“我能稳定写对哪个”。5. 完整代码哈希二分版可直接交5.1 代码主体下面是我按双哈希写的完整 C 代码可以直接套用。为了便于理解我尽量把结构写得清晰一点没有刻意压行。#include bits/stdc.h using namespace std; typedef long long ll; typedef pairll, ll pll; const ll MOD1 1000000007LL; const ll MOD2 1000000009LL; const ll BASE1 131LL; const ll BASE2 13331LL; struct DoubleHash { string s; int n; vectorll h1, h2, p1, p2; DoubleHash(const string _s) { s _s; n (int)s.size(); h1.assign(n 1, 0); h2.assign(n 1, 0); p1.assign(n 1, 1); p2.assign(n 1, 1); for (int i 1; i n; i) { p1[i] p1[i - 1] * BASE1 % MOD1; p2[i] p2[i - 1] * BASE2 % MOD2; h1[i] (h1[i - 1] * BASE1 s[i - 1]) % MOD1; h2[i] (h2[i - 1] * BASE2 s[i - 1]) % MOD2; } } pll get(int l, int r) const { ll v1 (h1[r] - h1[l - 1] * p1[r - l 1] % MOD1 MOD1) % MOD1; ll v2 (h2[r] - h2[l - 1] * p2[r - l 1] % MOD2 MOD2) % MOD2; return {v1, v2}; } }; // 比较 s1 的 [l1, r1] 和 s2 的 [l2, r2] // 如果前者的字典序 后者返回 true bool lessEqual(const DoubleHash hs1, int l1, int r1, const DoubleHash hs2, int l2, int r2) { int len1 r1 - l1 1; int len2 r2 - l2 1; int len min(len1, len2); int lo 0, hi len; while (lo hi) { int mid (lo hi 1) 1; if (hs1.get(l1, l1 mid - 1) hs2.get(l2, l2 mid - 1)) { lo mid; } else { hi mid - 1; } } if (lo len) { return len1 len2; } char c1 hs1.s[l1 lo - 1]; char c2 hs2.s[l2 lo - 1]; return c1 c2; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; string s; cin n s; string rev s; reverse(rev.begin(), rev.end()); DoubleHash hs(s); DoubleHash hr(rev); string ans; int l 1, r n; while (l r) { // 原区间 [l, r] 的反向区间在 rev 中是 [rl, rr] int rl n - r 1; int rr n - l 1; if (lessEqual(hs, l, r, hr, rl, rr)) { ans.push_back(s[l - 1]); l; } else { ans.push_back(s[r - 1]); r--; } } cout ans \n; return 0; }5.2 关键代码段的坑点注释我实际写这份代码时特别注意了几个地方。第一个是 DoubleHash 里的 get 函数。h1[l - 1] * p1[r - l 1]这一步必须先取模再减最后还要加上 MOD1 再取一次模。如果不加C 负数取模会得到负数结果导致哈希值永远对不上。第二个是二分里的 hi 初始值。如果 len 是 0这段代码会直接跳过循环但实际调用时区间长度至少是 1所以没问题。不过为了保险我会在调用前确认 l1 r1 且 l2 r2避免特殊情况下标越界。第三个是 ans 的拼接。每次 push_back 之前要小心是取 s[l-1] 还是 s[r-1]因为我的哈希结构里下标从 1 开始但原串 s 还是 0-index。这个转换关系写错了答案就会错得莫名其妙。5.3 边界用例自测清单我每次写完这类题都会跑一组自测数据覆盖几个容易出问题的场景用例ns期望输出单字符1AA两端相等但内部不同4BCABBBAA经典样例6ACDBCBABCBCD完全回文5ABCBAABCBA全部相同字符4AAAAAAAA严格递减4DCBAABCD特别是 “BCAB” 这个用例能立刻测出决策规则是否正确。如果代码直接输出 “BBAC” 而不是 “BBAA”说明你在两端相等时没有做正反串比较或者比较方向写反了。“DCBA” 对应的是每次都取右端的情况答案是升序 “ABCD”可以用来验证反向串始终更小这一分支。6. 排查实录这题最容易踩的五个坑6.1 base 和 mod 选不好哈希白写哈希模数我推荐直接用两个大质数比如 1e97 和 1e99。base 用 131、13331、911382323 这类常见值都可以。一个容易踩的坑是base 取得过大导致 base^len 在相乘时先溢出再取模。如果用了 long longbase 超过 1e9 后乘法结果很容易超过 64 位上限在取模之前就丢精度。所以要么直接选 131、13331 这种小 base要么每次乘法都写成((__int128)a * b) % mod。在普通校赛数据下131 和 13331 完全够用不需要冒险。还有某些题目字符集很小比如只有 0 和 1。这时 base 如果取 1哈希就会退化成区间字符和区分度极低。base131 是为了处理“字符的区分度”不能省。6.2 二分查找第一个不同字符的边界写错二分求 LCP 的经典写法是mid (lo hi 1) 1只有这种上取整写法才能避免“lo 和 hi 相邻时死循环”。我见过很多新手写成mid (lo hi) / 2然后当 lo0、hi1 时 mid0如果匹配成功lo 仍然等于 0永远不会收敛。比赛里死循环直接 TLE而且很难从样例里发现因为小数据可能碰巧不触发。另外hi 的初始值应该是 len这样当两个串完全相等时二分结果会稳定落在 len 上随后进入lo len分支。如果把 hi 设成 len - 1相等情况就会误判成“某个字符更小”答案就错了。6.3 反转串下标映射容易把人绕晕这是双哈希版本里最隐蔽的 bug原串[1..n] 的反向在 rev 中对应位置 rev[n - i 1]。所以原区间 [l, r] 反向后在 rev 中的区间是 [n - r 1, n - l 1]注意是左端点小、右端点大正好对应 rev 里的一个连续子串。很多同学会把 rev 中的左端点写成 n - l 1右端点写成 n - r 1直接用原区间的左右位置反向替换结果就查到了一个逆序的区间比较出来的字典序完全错误。我的建议是把原区间端点和反向端点写在一起对照类似这样原串位置: 1 2 3 4 5 6 原串字符: A C D B C B rev位置: 6 5 4 3 2 1 rev字符: B C B D C A当原区间是 [2, 5]字符 C D B C时rev 区间就是 [2, 5]字符 C B D C。每个位置单独映射一眼就能看出来哪边写反了。6.4 全相同字符和回文串场景当剩余区间是回文串时正反串字典序相等lessEqual 返回 true代码会稳定取左。这不会出错因为回文串从两端取得到的结果是一样的取左取右答案相同。但有一个隐藏风险如果整串全是同一个字符比如 “AAAA”每一步比较都会走完整二分耗时 O(log n)。n 大的时候这其实是“最坏情况下的每一步都要二分到底”。不过每次二分只有 log n 层整体 O(n log n) 对大多数题目都是可以接受的。如果这道题有 1e6 的全相同字符建议换成后缀数组方案避免二分常数的压力。另外回文场景下如果代码里用了单哈希且 base 选得很差理论上存在碰撞风险导致误判两个不同的串相等。双哈希就是用来兜住这类风险的。6.5 扩展思考最大字典序、数字序列、长度不同如果题目要求构造字典序最大的答案只需把 lessEqual 的方向反过来比较当前剩余区间和反向区间反向更大时取右端。如果输入是整数排列而不是字符串处理方式完全一样只要在 DoubleHash 的构造函数里把每个整数当成一个“字符”参与哈希即可。比较时对应位置比较 int 值而非 char 值二分逻辑不变。还有一类更复杂的变体两端取出的子串长度可以不同比如一次必须取 k 个字符。这时候“剩余区间”和“反向区间”可能长度不一致比较函数需要先处理长度差异如果其中一个串是另一个的前缀那么短串在字典序上更小。我上面写的 lessEqual 函数已经支持不同长度的子串比较后面遇到这种变体可以直接复用。最后的最后分享一个我在实际比赛中的体会这道题的决策规则“比较剩余串和反串”比想象中更容易推导真正的分水岭是能不能在半小时内写对哈希比较的细节。尤其是反转串下标映射和二分边界建议在编辑器里用“BCAB”和“ACDBCB”这两个用例做回归一遍跑过再交能省掉很多罚时。