后缀数组+二分答案 解洛谷P2852：height数组与最长重复子串

昨天把洛谷上的 P2852 [USACO06DEC] Milk Patterns G 这道信奥题过了趁着打卡系列整理一下思路。这道题在 USACO 2006 年 12 月的 Gold 组里算是很经典的“后缀数组 二分答案”入门题题面本身很朴素给你一个长度为 N 的整数序列求最长的连续片段长度使得这个片段在序列里至少出现 K 次片段之间允许重叠。N 最大 20000用 C 做最正统的解法就是后缀数组。我第一次看到这题时第一反应是能不能用滚动哈希加二分——理论上也能过但后来发现哈希解决不了扩展问题比如题目改成“片段不允许重叠”哈希就要写一堆额外判断。于是老老实实把后缀数组学了一遍P2852 也成了我理解 height 数组最好的素材。这篇文章会完整走一遍从拆题、选型到 AC 的流程适合刚开始刷后缀数组的选手。你只需要会排序、会写二分跟着思路走就能把这道题吃透。1. 题目到底在问什么——先别急着写代码1.1 一句话读懂题意P2852 的题面翻译过来并不复杂农夫记录了连续 N 天的牛奶质量每天的质量是一个 0 到 1000000 之间的整数现在要找一段“模式”——也就是连续若干天的质量序列——使得它在整段记录里至少出现 K 次并且模式之间允许重叠。要输出的就是满足条件的最长模式长度。举个例子就明白了。输入8 2 1 2 3 2 3 2 3 1这里 N8K2。肉眼扫一下“2 3”出现了 3 次“2 3 2 3”出现了 2 次分别是下标 1~4 和 3~6按 0 起始算这两处是重叠的。所以答案应该是 4。注意如果题目要求“不重叠”那“2 3 2 3”就只能算一次答案就会变。所以说“允许重叠”这个条件直接影响了算法设计读题时一定要圈出来。通过例子理解题意有个好处后面写 check 函数的时候你能直观知道自己在验证什么。很多人刷题上来就套模板套完才发现模板和题对不上就是这个环节跳太快了。1.2 为什么能一眼锁定后缀数组看到“子串出现次数”“最长”“可重叠”这三个关键词只要刷过几道后缀数组的题基本就该反应过来这是后缀数组加 height 数组的经典场景。原因在于后缀数组把“所有子串”变成了“所有后缀的前缀”而一个子串在文本中的每次出现都对应一个以它作为前缀的后缀。简单说后缀数组会先给所有后缀排个字典序排序之后拥有相同前缀的后缀会聚到一个连续区间里。于是“某个子串出现了几次”就变成了“后缀数组里一段连续区间有多长”。这个转换很重要后面所有的 check 逻辑都建立在这上面。你可能想问KMP 行不行KMP 是单模式串匹配这里模式串要动态枚举没法直接用。AC 自动机是处理多个已知模式串的本题模式串未知也不行。哈希加二分虽然能过题但哈希碰撞总让人心里不踏实而且一旦题目加个“输出具体模式”的扩展要求哈希会非常别扭。相比之下后缀数组是把这个问题的本质模型直接摆到桌面上所以是首选。1.3 算法的整体框架按我常用的流程这类题分三步走构建后缀数组 SA 和排名数组 rk根据 rk 构建 height 数组height 数组记录排名相邻的两个后缀的最长公共前缀长度LCP二分答案长度 L每次用 O(N) 的时间检查是否存在至少 K 个连续后缀它们两两之间的公共前缀都不小于 L。复杂度方面倍增加 sort 实现后缀数组是 O(N log²N)height 是 O(N)二分加 check 是 O(N logN)N20000 的情况下随便跑。如果你把后缀数组排序优化成基数排序可以压到 O(N logN)但题目数据量完全不需要先求稳更重要。接下来花点篇幅把后缀数组和 height 数组讲透因为这才是整道题的核心。2. 后缀数组与height数组这题真正的核心引擎2.1 后缀数组SA、排名数组rk到底在排什么后缀数组的定义很简单对一个整数序列的所有后缀按字典序排序排完后的下标序列就是 SA。比如序列“1 2 3 2 3 2 3 1”从位置 5 开始的后缀是“2 3 1”从位置 7 开始的后缀是“1”。把所有后缀从小到大排好SA[i] 就表示排名第 i 的后缀起点下标。反过来还有一个 rk 数组rk[i] 表示从下标 i 开始的后缀排名第几。SA 和 rk 是一一对应的互逆关系写代码时两个数组经常同时维护。用 STL 的话来感觉SA 是“第几名是谁”rk 是“我是第几名”。这里有个细节要注意做题的时候后缀数组下标到底从 0 开始还是从 1 开始不同模板不一样。我习惯用 0 起始这样 SA[i] 直接就是原数组下标比较直观。但代价是处理 height 数组时排名 0 的后缀没有前驱height[0] 要单独当成 0后面循环从 1 开始。这个细节看起来很小实际写的时候特别容易错我后面会专门讲。2.2 height数组把“出现K次”变成“连续一段”的关键height 数组的定义是height[i] LCP(sa[i-1], sa[i])也就是排名第 i 个后缀和排名第 i-1 个后缀的最长公共前缀长度。height[0] 没有定义通常置 0。为什么这个数组能解决出现次数问题这儿有个非常关键的性质对于任意两个后缀它们的 LCP 等于这两个后缀在排名区间内所有相邻 height 的最小值。这个性质可以类比成“水池里的水只取决于最矮的那块木板”。所以只要一段连续区间里的相邻 height 都不小于某个长度 L那这段区间内任意两个后缀至少共享一个长度为 L 的公共前缀。结合后缀数组的排序特性可以推出核心结论如果存在一个长度为 L 的子串出现了至少 K 次那么在后缀数组里一定存在连续至少 K 个后缀它们之间的相邻 height 都大于等于 L。反过来也成立。怎么理解“连续”假如某个子串 T 出现了很多次那么所有以 T 开头的后缀在字典序排序里必然会紧挨着排在一起因为任何不以 T 开头的后缀要么字典序比 T 小要么比 T 大不可能穿插在以 T 开头的两个后缀中间。“连续一段”这四个字是整个算法的灵魂。很多教程只会甩公式但如果你真跟上这步推导后面写 check 才能不懵。2.3 倍增法求SA的模板要点求后缀数组有很多实现倍增法是最容易理解的。核心思想是先按长度为 1 的子串排序再按长度为 2、4、8……排序每次用上一轮得到的排名来组合出一个新的二元组对二元组排序从而得到翻倍长度的排名。以长度为 step 为例每个后缀的排名可以用二元组 (rk[i], rk[istep]) 来表示越界部分用 -1 表示空串。第一个关键字是当前后缀从 i 开始的 step 个字符的排名第二个关键字是它后面 step 个字符的排名。当 step 翻倍时二元组涵盖的总长度就翻倍了。代码如下const int MAXN 20005; int sa[MAXN], rk[MAXN], tmp[MAXN]; int s[MAXN], n; void build_sa() { iota(sa, sa n, 0); sort(sa, sa n, [](int i, int j) { return s[i] s[j]; }); rk[sa[0]] 0; for (int i 1; i n; i) { rk[sa[i]] rk[sa[i - 1]] (s[sa[i]] ! s[sa[i - 1]]); } for (int step 1; rk[sa[n - 1]] n - 1; step 1) { auto cmp [](int i, int j) { if (rk[i] ! rk[j]) return rk[i] rk[j]; int ri i step n ? rk[i step] : -1; int rj j step n ? rk[j step] : -1; return ri rj; }; sort(sa, sa n, cmp); tmp[sa[0]] 0; for (int i 1; i n; i) { tmp[sa[i]] tmp[sa[i - 1]] (cmp(sa[i - 1], sa[i])); } copy(tmp, tmp n, rk); } }几点说明。第一初始排序直接按第一个元素排题目给的是整数序列int 比较没问题不用像字符串那样担心 ASCII。第二越界用 -1 表示空串任何非空后缀都比空串大这样字典序才是对的。第三循环终止条件是排名种数达到 n也就是所有后缀的排名都不同了。3. 二分答案 分组检查把复杂度压到O(N logN)3.1 二分可行性单调性从哪来现在我们要找最长长度自然想到二分。二分的先决条件是单调性如果存在一个长度为 L 的子串出现了至少 K 次那么它长度更短的前缀也一定出现了至少 K 次。所以“是否存在长度至少为 L 的合法子串”这个判断对 L 具备单调性L 越大越难满足L 越小越容易满足。于是问题变成了经典的“求最大的可行长度”可以二分。下界当然是 0上界设为 n因为子串长度不可能超过整个序列的长度。每次取 mid检查是否存在长度为 mid 的合法子串如果存在就往大试否则就往小试最后收敛到的就是答案。有些同学会担心上界设成 n 是不是太宽松会不会导致一些无意义的大长度影响效率。不会的因为 check 里一旦提前找到合法的情况就会立即返回 true而且二分总共也就 O(logN) 轮N 只有 2 万完全不构成压力。3.2 check函数的分组计数实现有了 height 数组check 就可以在 height 数组上扫一遍。具体做法是用一个计数器 cnt表示当前这组里已经连续多少个后缀满足“相邻 height 不低于 L”。cnt 从 1 开始因为单看一个后缀也算一组。从 i1 开始扫描 heightbool check(int len) { int cnt 1; for (int i 1; i n; i) { if (height[i] len) { cnt; if (cnt K) return true; } else { cnt 1; } } return false; }为什么这么写就对了因为 height[i] len 意味着排名第 i-1 和第 i 个后缀连长度为 len 的公共前缀都没有它们肯定不能待在同一个“共享长度为 len 前缀”的组里。一旦遇到这种断点就必须重新开始计数。而只要某个连续段里累计到 K 个后缀就说明存在长度至少为 len 的公共子串可以被这 K 个后缀共同拥有直接返回 true。理解这个 check 可以想象成一个分组的场景把一排后缀按 height 是否大于等于 len 分成若干组组内相邻后缀的公共前缀都大于等于 len组与组之间被断点隔开。题目等价于问有没有一组的人数达到 K。这个视角非常直观写起来也不容易错。3.3 二分边界与K1的隐藏坑二分模板我习惯用“可行最大值”型int lo 0, hi n; while (lo hi) { int mid (lo hi 1) / 2; if (check(mid)) lo mid; else hi mid - 1; } cout lo \n;注意 mid 的取整方向是向上取整。如果 check 返回 true说明 mid 可行答案至少是 mid所以 lo mid如果 check 返回 false说明 mid 太大答案最多是 mid-1所以 hi mid-1。这样写的好处是完全避免 lo 和 hi 相邻时的死循环。但这里有一个非常经典的坑K1 时任意子串都算出现一次最长的显然是整个序列的长度 n。可是如果直接走 check(1)在分组计数时因为 height 不一定都大于等于 1cnt 会被反复重置很可能永远达不到 K最终返回 false。所以必须特判if (K 1) { cout n \n; return 0; }我第一次提交 WA就是栽在这个 K1 上。题目确实允许 K1别因为测试样例里没给就忽略。当然你也可以在 check 开头加一句 if (K 1) return true两种处理都行我习惯在 main 里特判逻辑更直白。4. 完整AC代码与验证过程4.1 可复现的完整C实现把上面的模板拼起来就是一份可以直接提交的完整代码#include bits/stdc.h using namespace std; const int MAXN 20005; int n, K; int s[MAXN]; int sa[MAXN], rk[MAXN], tmp[MAXN]; int height[MAXN]; void build_sa() { iota(sa, sa n, 0); sort(sa, sa n, [](int i, int j) { return s[i] s[j]; }); rk[sa[0]] 0; for (int i 1; i n; i) { rk[sa[i]] rk[sa[i - 1]] (s[sa[i]] ! s[sa[i - 1]]); } for (int step 1; rk[sa[n - 1]] n - 1; step 1) { auto cmp [](int i, int j) { if (rk[i] ! rk[j]) return rk[i] rk[j]; int ri i step n ? rk[i step] : -1; int rj j step n ? rk[j step] : -1; return ri rj; }; sort(sa, sa n, cmp); tmp[sa[0]] 0; for (int i 1; i n; i) { tmp[sa[i]] tmp[sa[i - 1]] (cmp(sa[i - 1], sa[i])); } copy(tmp, tmp n, rk); } } void build_height() { int h 0; for (int i 0; i n; i) { if (rk[i] 0) continue; int j sa[rk[i] - 1]; while (i h n j h n s[i h] s[j h]) h; height[rk[i]] h; if (h) h--; } } bool check(int len) { int cnt 1; for (int i 1; i n; i) { if (height[i] len) { cnt; if (cnt K) return true; } else { cnt 1; } } return false; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n K; for (int i 0; i n; i) cin s[i]; build_sa(); build_height(); if (K 1) { cout n \n; return 0; } int lo 0, hi n; while (lo hi) { int mid (lo hi 1) / 2; if (check(mid)) lo mid; else hi mid - 1; } cout lo \n; return 0; }这份代码我本地和洛谷都跑过C17 直接编译通过。要注意的是build_height 里用了 height[rk[i]]所以 height 数组要和 rk、sa 严格对应。只要 build_sa 没问题height 构建基本不会出大错。4.2 手算样例跑一遍算法纸上模拟一遍最能验证理解。还是用那个样例8 2 1 2 3 2 3 2 3 1所有后缀按字典序排序后SA 数组如下排名后缀起点后缀内容height0710101 2 3 2 3 2 3 11252 3 10332 3 2 3 12412 3 2 3 2 3 14563 10643 2 3 11723 2 3 2 3 13height 数组就是0 1 0 2 4 0 1 3。现在验证 check(4)。扫描 height只有 height[4] 4 大于等于 4所以 cnt 从 1 开始到 i4 时变成 22 K2返回 true。再看 check(5)所有 height 都不大于等于 5返回 false。所以二分收敛到 4答案 4和手算一致。注意排名 4 和排名 3 的后缀分别是“2 3 2 3 2 3 1”和“2 3 2 3 1”它们的公共前缀长度正好是 4这就是答案子串“2 3 2 3”。这两个后缀起始位置是 1 和 3对应的子串也确实在原序列里出现了两次。4.3 随机数据对拍把正确性焊死模板题最怕的就是代码看着对、样例也对提交后却 WA。我强烈建议对拍。对拍的思路是写一个正确的暴力解法然后不断生成随机数据比较暴力解和正解的输出。暴力解可以这样写枚举所有子串长度 len把所有长度为 len 的连续片段取出来统计出现次数只要某个片段出现次数达到 K 就更新答案。N20000 时暴力会非常慢但没关系对拍时生成小数据比如 N 不超过 20K 不超过 5暴力也能跑完。核心暴力函数可以直接用 STL 写int brute(int arr[], int n, int k) { int ans 0; for (int len 1; len n; len) { mapvectorint, int cnt; for (int i 0; i len n; i) { cnt[vectorint(arr i, arr i len)]; } for (auto p : cnt) { if (p.second k) ans max(ans, len); } } return ans; }生成随机数据的代码思路int main() { int n rand() % 15 1; int k rand() % n 1; cout n k \n; for (int i 0; i n; i) cout rand() % 5 ; }值域控制在 0 到 4能增加重复模式的概率更容易暴露错误。然后把暴力程序和后缀数组程序同时跑比较输出结果。我刷题这几年凡是对拍能跑几百组不出错的模板提交基本就稳了。这个习惯对信奥选手来说非常值钱。5. 提交WA自救指南常见坑位与调试心得5.1 下标、命名、height初始化这题的坑很大一部分集中在下标和命名上。第一用 0 起始下标时height[0] 没有定义循环必须从 i1 开始不然会把 height 里残留的 0 或者垃圾值扫进去。第二build_sa 里循环变量 step 千万别和题目的 K 重名。我有一版代码就把 step 写成了 k结果函数里局部 k 和全局 K 混在一起排查了半天。建议固定命名为 step 或者 p不要用 k。第三height 构建过程中用了变量 h注意它的递减只在 h 大于 0 时进行这是后缀数组 height 线性求解的关键千万别去掉。还有一个小地方build_sa 时初始排序如果不用 iota也可以直接循环赋值 0 到 n-1但 iota 写起来更干净。sort 的 lambda 捕获 step 时用 [] 捕获所有外部变量别用 []因为 step 在循环里会变[] 才能保证取到最新值。5.2 整数序列处理与读入性能问题题目给定的序列是整数不是字符。很多人默认是字符串结果把 0 当成结束符或者用 char s[MAXN] 之后发现数字越界。这道题直接开 int 数组存后缀之间的比较就用 int 值比天然满足“字典序”的要求。如果你以前只写过字符串后缀数组这里要适应一下字符串版本的排序通常把字符转换成 ASCII 码或者做离散化整数版本则直接比较 int 值效果完全等价。值域上限 1000000 不影响 int 排序。至于要不要离散化这题没有必要因为比较的是元素大小而不是桶下标。只有在你想用基数排序优化的版本里才会考虑把值域压小。输入输出节奏也值得提。洛谷的测评机对 cin/cout 很宽容但加了 ios::sync_with_stdio(false) 和 cin.tie(nullptr) 之后会更稳。如果你在 Windows 本地用 VSCode 配环境总出问题建议直接装 MinGW-w64或者用 Dev-C 这类开箱即用的 IDE先把算法本身跑通环境问题不要浪费太多时间。5.3 从这题延伸出去同类模型迁移这道题解决之后后缀数组的模型基本上就打通了。稍微改一改能迁移到很多同类题如果要求“不可重叠地出现 K 次”check 时不能只看 height 分组还要维护同一组内 SA 的最大值和最小值判断 max - min 是否大于等于 len这个条件能保证找到的子串之间不重叠。如果要求“至少出现 2 次的最长重复子串”就是 K2 的弱化版直接用本题代码把 K 设成 2 即可。如果求“不同子串的个数”答案是所有后缀长度之和减去 height 数组之和这是后缀数组里的经典结论。如果只是后缀排序模板那就是洛谷 P3809那是所有后缀数组题的基础。从信息学竞赛的角度看P2852 的价值在于它把“子串出现次数”和“height 数组分组”这两个概念绑定到了一起。理解了这道题后面遇到类似问题就能快速想起这个套路而不是重新从零推导。这也是我为什么建议你把它当成后缀数组入门后的第一道应用题。最后说点个人的体会。我最早做这题时想的是滚动哈希加二分过了样例交上去却因为哈希碰撞翻车。后来复盘才发现自己没有真正理解“出现 K 次”在后缀数组里的结构。现在回头看这道题让我最受益的不是记住了后缀数组的模板而是学会了把“子串出现次数”转化为“后缀数组上的连续区间长度”再用 height 数组去验证。建议你先把 P3809 后缀排序模板刷到能默写再来做 P2852会顺畅很多。刷题打卡这种东西重要的不是数量而是每道题能沉淀出什么。就冲这道题我觉得值得好好写一篇。