后缀数组+二分答案 解洛谷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

这里 N=8，K=2。肉眼扫一下，“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 算法的整体框架

按我常用的流程，这类题分三步走：

1. 构建后缀数组 SA 和排名数组 rk；
2. 根据 rk 构建 height 数组，height 数组记录排名相邻的两个后缀的最长公共前缀长度（LCP）；
3. 二分答案长度 L，每次用 O(N) 的时间检查是否存在至少 K 个连续后缀，它们两两之间的公共前缀都不小于 L。

复杂度方面，倍增加 sort 实现后缀数组是 O(N log²N)，height 是 O(N)，二分加 check 是 O(N logN)，N=20000 的情况下随便跑。如果你把后缀数组排序优化成基数排序，可以压到 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[i+step]) 来表示，越界部分用 -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 开始，因为单看一个后缀也算一组。

从 i=1 开始扫描 height：

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; }

为什么这么写就对了？因为 height[i] < len 意味着排名第 i-1 和第 i 个后缀连长度为 len 的公共前缀都没有，它们肯定不能待在同一个“共享长度为 len 前缀”的组里。一旦遇到这种断点，就必须重新开始计数。而只要某个连续段里累计到 K 个后缀，就说明存在长度至少为 len 的公共子串，可以被这 K 个后缀共同拥有，直接返回 true。

理解这个 check 可以想象成一个分组的场景：把一排后缀按 height 是否大于等于 len 分成若干组，组内相邻后缀的公共前缀都大于等于 len，组与组之间被断点隔开。题目等价于问有没有一组的人数达到 K。这个视角非常直观，写起来也不容易错。

3.3 二分边界与K=1的隐藏坑

二分模板我习惯用“可行最大值”型：

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 相邻时的死循环。

但这里有一个非常经典的坑：K=1 时，任意子串都算出现一次，最长的显然是整个序列的长度 n。可是如果直接走 check(1)，在分组计数时，因为 height 不一定都大于等于 1，cnt 会被反复重置，很可能永远达不到 K，最终返回 false。所以必须特判：

if (K == 1) { cout << n << "\n"; return 0; }

我第一次提交 WA，就是栽在这个 K=1 上。题目确实允许 K=1，别因为测试样例里没给就忽略。当然，你也可以在 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; }

这份代码我本地和洛谷都跑过，C++17 直接编译通过。要注意的是，build_height 里用了 height[rk[i]]，所以 height 数组要和 rk、sa 严格对应。只要 build_sa 没问题，height 构建基本不会出大错。

4.2 手算样例跑一遍算法

纸上模拟一遍最能验证理解。还是用那个样例：

8 2 1 2 3 2 3 2 3 1

所有后缀按字典序排序后，SA 数组如下：

height 数组就是：0 1 0 2 4 0 1 3。

现在验证 check(4)。扫描 height：只有 height[4] = 4 大于等于 4，所以 cnt 从 1 开始，到 i=4 时变成 2，2 >= K=2，返回 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 就更新答案。N=20000 时暴力会非常慢，但没关系，对拍时生成小数据，比如 N 不超过 20，K 不超过 5，暴力也能跑完。

核心暴力函数可以直接用 STL 写：

int brute(int arr[], int n, int k) { int ans = 0; for (int len = 1; len <= n; len++) { map<vector<int>, int> cnt; for (int i = 0; i + len <= n; i++) { cnt[vector<int>(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] 没有定义，循环必须从 i=1 开始，不然会把 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 次的最长重复子串”，就是 K=2 的弱化版，直接用本题代码把 K 设成 2 即可。
• 如果求“不同子串的个数”，答案是所有后缀长度之和减去 height 数组之和，这是后缀数组里的经典结论。
• 如果只是后缀排序模板，那就是洛谷 P3809，那是所有后缀数组题的基础。

从信息学竞赛的角度看，P2852 的价值在于它把“子串出现次数”和“height 数组分组”这两个概念绑定到了一起。理解了这道题，后面遇到类似问题就能快速想起这个套路，而不是重新从零推导。这也是我为什么建议你把它当成后缀数组入门后的第一道应用题。

最后说点个人的体会。我最早做这题时，想的是滚动哈希加二分，过了样例，交上去却因为哈希碰撞翻车。后来复盘，才发现自己没有真正理解“出现 K 次”在后缀数组里的结构。现在回头看，这道题让我最受益的不是记住了后缀数组的模板，而是学会了把“子串出现次数”转化为“后缀数组上的连续区间长度”，再用 height 数组去验证。建议你先把 P3809 后缀排序模板刷到能默写，再来做 P2852，会顺畅很多。刷题打卡这种东西，重要的不是数量，而是每道题能沉淀出什么。就冲这道题，我觉得值得好好写一篇。