2026/9/20 3:55:14
FEATURED · 精选文章 
有一说一信奥刷题这事儿最怕的不是题不会做而是“看了一堆题解代码抄了一遍换道题还是不会”。P2852 [USACO06DEC] Milk Patterns G 这题就很典型——它表面上是一道USACO老题实际是后缀数组Suffix Array这个知识点的标准敲门砖。你要是能把这道题吃透后缀数组的height数组、二分答案、区间最值这些套路基本就通了。这篇文章就围绕这个题把每一步怎么想、为什么这么做、代码怎么写、坑在哪一次聊透。题目本身不复杂给一个长度为N的整数序列N最大20000要找出至少出现K次的最长可重叠子串长度。这里的“可重叠”三个字很关键因为一旦允许重叠很多暴力做法就失效了你必须用后缀数据结构去解。这道题在洛谷上是提高/省选-的难度但实际考的就是两个核心能力一是能不能把“最长重复子串”转化为“后缀数组height数组的区间最小值问题”二是能不能把二分答案的check函数写明白。我见过不少选手卡在这题上其实不是后缀数组模板不会写而是卡在“为什么答案是连续K-1个height的最小值的最大值”这句话上。下面我直接把整道题的拆解、原理、代码和调试经验都写出来思路按“从题目到算法再到实现”的顺序走适合刚学完后缀数组、想用一道题夯实基础的选手也适合准备NOIP提高组、USACO Gold及以上级别考试的人。1. 题目拆解与核心考点分析1.1 题目到底在问什么Milk Patterns G 的题面大意是农夫约翰记录了N头牛的牛奶产量每个产量是一个整数他想找出“至少出现K次”的最长模式串长度。这里“模式串”指的是连续的一段产量序列比如[1, 2, 3]在整段数据里出现了K次以上那么长度3就是一个候选答案要求的是最大的这种长度。几个关键细节必须先拎清楚N最大是20000这个规模决定了 O(N^2) 级别的暴力在极限数据下是扛不住的。每个产量数值范围没说得很小原题数值可能很大所以不能直接把数值当下标用要做离散化或者用哈希处理。至少有K次K可能等于1。如果K1答案就是N这个特判如果漏了会直接WA。子串之间允许重叠。比如序列1 1 1中子串1出现3次可重叠子串11出现2次也是可重叠的。这个条件决定了你不能用KMP那种找不重叠模式串的思路去做。1.2 一个关键转化子串就是“后缀的前缀”后缀数组这个数据结构处理“子串”问题核心思路是任意一个子串一定是某个后缀的前缀。举个例子对于数组[1, 2, 3, 1, 2]后缀从下标0开始是[1, 2, 3, 1, 2]从下标3开始是[1, 2]。子串[1, 2]既是第一个后缀的前缀也是第四个后缀的前缀。如果一个子串出现K次就意味着至少有K个后缀的前缀都等于这个子串。在排好序的后缀数组中拥有相同前缀的后缀一定排在相邻的位置。所以如果某个长度为L的子串出现了至少K次那么在后缀数组的排序结果里一定有连续K个后缀它们两两之间的LCP最长公共前缀长度都至少是L。这就引出了height数组height[i] 表示排名第i的后缀和第i-1的后缀的最长公共前缀长度。那么“有连续K个后缀两两LCP L”就等价于“存在连续K-1个height值都 L”。这个转化是整个题目的灵魂。理解了这一步后面要么二分答案要么滑动窗口都能展开。1.3 这道题适合放在什么学习阶段如果你已经能独立写出后缀数组的O(N log N)倍增模板那这道题是极好的“模板落地题”。它能让你从“会抄模板”进阶到“会用模板”。如果你还不会后缀数组这道题也是一个不错的入手点因为它的核心查询逻辑不复杂不需要会后缀自动机也不需要会后缀树只要把SA和height求出来问题就变成了一个纯粹的数组区间判断问题。相比直接刷P3809后缀排序模板题那种纯模板题P2852更接近真实竞赛的应用场景。2. 算法选型与原理推导为什么后缀数组是首选2.1 候选方案对比遇到“最长重复子串”这一类问题通常有几条路线可以走方案构建复杂度查询/判定复杂度代码量风险点暴力枚举长度 hashO(N^2) 或 O(N log N) 枚举O(N) 或 O(N log N)中等哈希碰撞且需要精细设计KMP / Z 函数O(N)只能处理固定模式串低本题是求“任意子串”无法直接套后缀数组 SA 二分O(N log N)check 为 O(N)二分 O(log N)较高边界处理要仔细后缀自动机 SAMO(N)O(N)高节点概念较重内存多后缀树O(N)O(N)很高一般不直接用对竞赛场景来说后缀数组这条路最稳代码是固定的模板思维难度集中在“如何把原问题转为height数组问题”而这恰恰是想考察的能力。2.2 二分答案的可行性长度为L的子串出现了至少K次那么长度L-1的子串也一定出现了至少K次把那个长度为L的子串去掉最后一个元素就行。所以答案具有单调性——如果L可行比L小的也一定可行。既然有单调性就可以二分答案。二分下界是1上界是N。每次二分一个mid去检查“是否存在长度为mid的子串至少出现K次”。check的复杂度如果能做到O(N)那么整体就是O(N log N)在N20000时非常宽裕甚至N100000也能跑得动。2.3 为什么不能用KMPKMP 擅长的是“给定一个模式串找它在文本串里出现了几次”。但这道题的模式串是未知的需要你去找“满足出现次数要求的最长模式串”。如果用KMP你必须枚举模式串的起点和长度复杂度直接爆炸。后缀数组的价值就在于它一次性把所有后缀的公共前缀关系都组织好了不需要再枚举模式串。2.4 对“可重叠”这件事height数组天然支持很多人会想可重叠是不是比不可重叠更难其实在height数组的语义里“两个后缀的LCP”天然就是允许重叠的。因为LCP计算的是两个后缀从头开始最多能匹配多少位重叠与否根本不进入比较逻辑。所以这个题要求“可重叠”反而让代码更简单。如果题目变成“不可重叠的最长重复子串”那还得额外记录每个height区间对应的起点最小值和最大值判断是否重叠工作量明显更大。3. 核心细节SA与height数组的构建与理解3.1 后缀数组构建模板的选型C选手写后缀数组常用的是倍增法O(N log N)。模板框架以罗穗骞论文版为基础我在实际刷题中一般保存一套稳定的结构体版本struct SuffixArray { int n; vectorint sa, rk, ht; // sa[i]: 排名为i的后缀的起始下标从0开始 // rk[i]: 起始下标为i的后缀的排名 // ht[i]: 排名为i的后缀与排名为i-1的后缀的LCP长度 SuffixArray(const vectorint s) { n (int)s.size(); sa.resize(n); rk.resize(n); ht.resize(n); // 实现略见下方完整代码 } };3.2 构建SA时为什么需要离散化模板内部通常要对字符集开桶进行基数排序。如果序列中的数值范围很大比如1e9直接开桶数组会爆内存。两个解决办法使用map离散化把数值映射成0到m-1的排名。使用 unordered_map 排序去重然后二分查找或lower_bound得到离散化后的值。在P2852中N只有20000离散化成本极低。离散化还有一个额外好处如果两个位置的数值相同离散化的值也相同这样后缀比较时能保留原始相等关系不影响排序结果。3.3 height数组的求法与性质height数组有两条求法定义法对相邻排名后缀暴力求LCPO(N^2)。性质法利用ht[rk[i]] ht[rk[i-1]] - 1这条重要性质可以在O(N)时间内递推求出。这个性质懂不懂都行模板背下来就好。height数组最核心的性质是排名相邻的两个后缀的LCP就是height值任意两个后缀排名为i和j的LCP等于 min(ht[i1..j])。也就是说height数组是后缀数组上区间查询“公共前缀”的基础。回到本题要判断长度为mid的子串是否至少出现K次就是判断是否有一段连续的K-1个height值全部 mid。因为一旦有连续K个后缀的LCP都 mid就表明这些后缀共享一个长度为mid的公共前缀即这个前缀在原始序列中作为子串出现了K次。3.4 对height数组的一个直觉理解想象一排后缀排好队height[i] 是第i个人和第i-1个人之间的共同前缀长度。现在要找“至少K个人都认识同一个长度为L的暗号”只需要看“是否有连续的K-1个间隙都 L”。如果一个人和前面的人能共享L长度的暗号那他就属于这个群体如果某个间隙小于L这个群体就在这里断开了。这个直觉很重要。很多初学者总是想着“怎么从height数组里找出K个后缀”其实不用找K个只要看K-1个间隙就行。因为这K个后缀是连续的它们之间的K-1个间隙都必须 L这是一个充分必要条件。4. 实操实现完整C代码与逐段解读4.1 读入细节这题的输入是N和K然后是N个整数。但是原题有一个坑N和K不一定在同一行后面的N个整数也可能分布在多行。所以必须用cin x这样自动跨空白读的方式不要用scanf加固定格式假设每一行恰好多少个数。4.2 完整代码#include bits/stdc.h using namespace std; struct SuffixArray { int n; vectorint sa, rk, ht; SuffixArray(const vectorint s) { n (int)s.size(); sa.assign(n, 0); rk.assign(n, 0); ht.assign(n, 0); // 第一轮排序按单个字符排名 vectorint cnt(max(n, 256), 0); for (int i 0; i n; i) cnt[s[i]]; for (int i 1; i (int)cnt.size(); i) cnt[i] cnt[i - 1]; for (int i n - 1; i 0; i--) sa[--cnt[s[i]]] i; rk[sa[0]] 0; int classes 1; for (int i 1; i n; i) { if (s[sa[i]] ! s[sa[i - 1]]) classes; rk[sa[i]] classes - 1; } // 倍增排序 vectorint sa2(n), rk2(n); for (int k 1; classes n; k 1) { int p 0; // 按第二关键字排序起点 n-k 的第二关键字为 -1排最前 for (int i n - k; i n; i) sa2[p] i; for (int i 0; i n; i) { if (sa[i] k) sa2[p] sa[i] - k; } // 按第一关键字基数排序 fill(cnt.begin(), cnt.begin() classes, 0); for (int i 0; i n; i) cnt[rk[sa2[i]]]; for (int i 1; i classes; i) cnt[i] cnt[i - 1]; for (int i n - 1; i 0; i--) { int x sa2[i]; sa[--cnt[rk[x]]] x; } // 计算新的 rank rk2[sa[0]] 0; classes 1; for (int i 1; i n; i) { int cur sa[i], prev sa[i - 1]; if (rk[cur] ! rk[prev] || (cur k n ? rk[cur k] : -1) ! (prev k n ? rk[prev k] : -1)) classes; rk2[cur] classes - 1; } rk.swap(rk2); if (classes n) break; } // 求 height 数组 int h 0; for (int i 0; i n; i) { if (rk[i] 0) { ht[0] h 0; continue; } int j sa[rk[i] - 1]; while (i h n j h n s[i h] s[j h]) h; ht[rk[i]] h; if (h) h--; } } }; bool check(const SuffixArray sa, int len, int k) { // 检查是否存在至少 k 个后缀其公共前缀长度 len // 等价于是否存在连续 k-1 个 height 值都 len int cnt 1; // 当前连续满足 height len 的后缀数量 for (int i 1; i sa.n; i) { if (sa.ht[i] len) { cnt; if (cnt k) return true; } else { cnt 1; } } return false; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, k; cin n k; vectorint a(n); for (int i 0; i n; i) cin a[i]; if (k 1) { cout n \n; return 0; } // 离散化 vectorint vals a; sort(vals.begin(), vals.end()); vals.erase(unique(vals.begin(), vals.end()), vals.end()); for (int i 0; i n; i) { a[i] lower_bound(vals.begin(), vals.end(), a[i]) - vals.begin(); } SuffixArray SA(a); // 二分答案 int l 1, r n; int ans 0; while (l r) { int mid (l r) 1; if (check(SA, mid, k)) { ans mid; l mid 1; } else { r mid - 1; } } cout ans \n; return 0; }4.3 关键点逐段说明离散化部分vectorint vals a; sort(vals.begin(), vals.end()); vals.erase(unique(vals.begin(), vals.end()), vals.end()); for (int i 0; i n; i) { a[i] lower_bound(vals.begin(), vals.end(), a[i]) - vals.begin(); }这个离散化写起来很舒服但要注意lower_bound是 O(log n) 的对于 20000 的数据量完全没问题。离散化后数值范围变成了 0 到 m-1m n这样 SA 模板内部的计数数组大小就能控制在 O(n) 级别。check 函数部分int cnt 1; for (int i 1; i sa.n; i) { if (sa.ht[i] len) { cnt; if (cnt k) return true; } else { cnt 1; } }cnt 的初始值是1这代表第一个后缀自己算一个。height[i] 是第i个后缀和第i-1个后缀的公共前缀所以当 height[i] len 时第i个后缀也加入了“公共前缀长队”cnt加1。遇到小于len的说明队伍断了重新计数。这个写法比“统计连续段长度再检查”更简洁副作用也少。K1特判如果 K1要求出现至少1次的最长子串答案显然是N。不特判的话check(1) 也会返回true但二分会找到N逻辑上其实能过。但某些二分写法可能在边界上出问题所以显式特判更稳妥还能减少不必要的 SA 构建不过代码里已经先构了SA特判放后面也没问题注意顺序。我实际提交过一版把特判放在 SA 构建之前更省时间。上面为了展示流程放在了 SA 之后这也说明数据规模很小放哪都行。4.4 为什么倍增排序里第二关键字可以直接“移位”在倍增排序中第二关键字其实是“从位置 i k 开始的后缀的第一关键字”。代码里for (int i n - k; i n; i) sa2[p] i; for (int i 0; i n; i) { if (sa[i] k) sa2[p] sa[i] - k; }第一行把后缀起点在 [n-k, n-1] 的放最前面因为它们的第二关键字是“空串”比较时最小。第二行的逻辑是当前长度为k时排名第i的后缀sa[i]它作为第二关键字对应到的“母后缀”起点是sa[i] - k也就是以sa[i]-k开头的后缀其第二关键字就是sa[i]开头的后缀的排名。这个手法是倍增法的精髓这里不展开全部证明但理解它有助于后续调试。如果你不想费劲理解倍增法直接背模板也没问题。不过建议至少模拟一遍N5的小样例否则SA结果错误时你完全没法debug。5. 多个角度验证手动模拟样例5.1 样例输入8 2 1 2 3 2 3 2 3 1这个样例中序列是1 2 3 2 3 2 3 1K2问至少出现2次的最长子串。人工看一下子串2 3 2 3出现了2次下标1和3长度4再长的子串没有出现2次。所以答案是4。下面看看算法路径。5.2 SA 与 height核心字段以这个样例离散化后排序SA以及height大致如下具体排名可能因模板细节略有差异但 heights 的集合不变排名 i后缀起点后缀内容height[i]0710101 2 3 2 3 2 3 11222 3 2 3 13342 3 12463 11512 3 2 3 2 3 14632 3 2 3 13752 3 12注意这里的排名是我按字典序行的排列不要纠结具体顺序重点是 height 数组中出现了连续段4, 3这意味着排名5和6的两个后缀共享长度为4的公共前缀排名6和7共享长度3——连续两个 height 都 2就代表至少3个后缀之间有足够长的公共前缀……不过K2时只需要连续1个height mid即可也就是存在两个后缀LCP mid。二分mid4时height数组里是否有 4 的值有排名5和6之间的4所以返回true。mid5时没有height 5返回false。所以答案是4。5.3 检查“至少出现K次”和“连续K-1个height L”的等价性以K3为例假设某个L2。height数组中连续两个值 2 的情况排名1和2的height是3排名2和3的height是2所以排名1、2、3三个后缀共享了长度至少2的公共前缀。查一下排名1、2、3对应的内容2 3 2 3 2 3 1、2 3 2 3 1、2 3 1它们的前缀都是2 3出现3次所以L2可行。可见“连续K-1个height L”这个条件准确捕捉到了至少K个后缀共享长度L的前缀。5.4 一个容易踩的坑height[0] 的定义height[0] 通常定义为0因为排名第0的后缀没有前一个。check 循环从 i1 开始就自动绕过了 height[0]。如果你从 i0 开始会造成 cnt 多算一个答案偏大这是很隐蔽的WA原因。我见过有人卡这个坑卡了很久。6. 常见问题与排查技巧实录6.1 编译环境问题热词里有人提到“Microsoft Visual C 14.0 required”之类的问题——这是 Windows 环境装 Python 包时常见的报错和信奥常用环境不同。信奥场景下本地用 Dev-C 或 VS Code 配置 C 环境即可注意把标准设为 C14 或 C17因为代码里用了auto、vector初始化等现代特性。如果你在 VS Code 里跑一个小建议把cppStandard设为c17否则某些编译器默认用老的 C98 标准vectorint cnt(max(n, 256), 0)这种写法在旧标准里也能跑但auto不行容易报错。另一个和编译相关的问题是“数组越界”。后缀数组模板里cnt的大小需要至少覆盖字符集大小和n如果离散化后的最大值是 m但 cnt 开成 n 而不是 max(n, m)1某些实现会越界。我的模板里用max(n, 256)确保万无一失。6.2 SA构建结果不对怎么排查SA模板写错通常表现为排序结果不稳定或者height数组求出来是负数、极大值。排查步骤先用一个已知的小数组测试比如aabaaaab或{1, 1, 1}手动写出所有后缀的字典序对比SA结果。检查离散化后的数组值是否连续从0开始。如果中间跳过了某个值计数排序的 classes 会乱但通常不影响最终顺序只是排名值不连续会让 height 数组的某些边界判断出错。检查rk和sa的对应关系sa[rk[i]] i必须成立。检查 height 是否满足ht[rk[i]] ht[rk[i-1]] - 1这条性质。如果不满足说明height的计算过程有错。6.3 二分边界怎么写不死循环二分答案有几种模板我习惯用l1, rn; while (l r)。这个写法要求最后输出 ansint l 1, r n; int ans 0; while (l r) { int mid (l r) 1; if (check(mid, k)) { ans mid; l mid 1; } else { r mid - 1; } }这种写法不容易死循环。如果你用while (l r)的写法注意 mid 的取整方向否则在 l4, r5 时可能反复横跳。我建议新手中途不要自行改版先用熟一种。6.4 注意 cin 的读取效率N20000数据量不大cin加ios::sync_with_stdio(false)足够。如果以后刷到 N1e6 级别的题还是建议用scanf或手写快读。不过手写快读在对付负数时要注意符号这里不展开。6.5 不要忘记多组数据这题没说有多组数据但USACO的部分题有多个文件的输出要求文件IO。我提交时习惯把 freopen 注释掉因为洛谷是在标准IO下评测的。如果你用USACO官方数据测试注意读文件名是p2852.in和p2852.out还是milk.in等要看题目具体要求。P2852在洛谷上是标准IO直接用cin/cout就行。6.6 一个容易被忽略的边界所有数都一样假设输入是5 3和1 1 1 1 1。此时任意长度的子串都出现至少3次答案应该是5。实测一下height数组全是4排名相邻的两个相同后缀LCP为4。check(5)时height[i] 5 吗不成立返回false。这会导致二分答案结果为4而不是5。等等这难道不是WA吗这里要特别小心序列长度为5子串最大长度就是5但是“出现至少3次的最长子串”如果是整个序列它只出现1次不满足K3。所以要找的是“长度1且出现3次的最长子串”而长度为5的整个序列只出现一次当然不行。长度为4的子串1 1 1 1出现2次下标0和1还是不满足K3。长度为3的1 1 1出现3次满足。所以正确答案是3不是5。这个例子正好说明了为什么不能无脑把答案输出成n——重复子串的长度上限不是n而是“出现k次的那个子串最长能有多长”。在这个例子中height数组全是4但K3需要的是连续2个height都 mid。mid3时连续两个height 3 成立mid4时连续两个height 4 也成立可是长度为4的子串只出现2次K3时不满足啊这里就要回去看等价性条件连续3个后缀的LCP都 4才说明有一个长度为4的子串出现3次。如果height数组是[0, 4, 4, 4, 4]那么连续两个height 4 表明有3个后缀两两LCP 4例如排名1、2、3三个后缀它们的公共前缀长度为4。排一下序所有后缀分别是[1,1,1,1,1],[1,1,1,1],[1,1,1],[1,1],[1]。排名1是[1,1,1,1]排名2是[1,1,1]排名3是[1,1]……等等height[1]是排名1和排名0的LCP4不对因为排名0是[1]和它LCP4的只有[1,1,1,1,1]这里我排错了。手动排序五个后缀起始0:[1,1,1,1,1]起始1:[1,1,1,1]起始2:[1,1,1]起始3:[1,1]起始4:[1]按字典序从小到大[1](起4),[1,1](起3),[1,1,1](起2),[1,1,1,1](起1),[1,1,1,1,1](起0)。所以height数组是ht[0] 0ht[1] 1 (起4和起3的LCP1)ht[2] 2ht[3] 3ht[4] 4对于K3要求连续2个height mid。mid4时没有任何连续2个height 4因为只有一个4。mid3时ht[2]2不行ht[3]3ht[4]4连续两个是3和4但3 4 的公共前缀是3 4等一下连续两个 height 3 是 ht[3]3 和 ht[4]4这表示排名3、4、5也就是起1、起0、起2三个后缀的LCP 3它们都有一个长度为3的公共前缀[1,1,1]。所以答案3成立。这个例子说明连续K-1个height都 mid 的条件本质上是在要求“这K-1个间隙所连接起来的K个后缀都共享同一个长度为mid的前缀”。最后一个后缀可能长度只有4所以公共前缀最大只有4但由于K3需要的是第1、2、3这三个后缀之间的间隙即ht[3]和ht[4]要同时3才行。上面的模拟完全吻合。6.7 洛谷与USACO评测的差异USACO原题的输出是写到文件里的文件名通常是milk.out。洛谷进行了重制改为标准输入输出。如果你在洛谷上做这道题切记不要保留freopen(milk.in, r, stdin)否则会等待文件输入直接超时。如果你自己下载USACO官方数据做测试就加上文件IO。这种细节在真实比赛中也常见值得养成“看清楚评测环境”的习惯。7. 进阶思考这题还能怎么变7.1 如果K很大的时候K越大满足条件的高度阈值就越高二分答案的上界其实可以收紧到n / K甚至更小但一般没必要。N20000时二分到n也就多几次check而已。7.2 如果要求“不可重叠”怎么办上面提过不可重叠需要额外维护每个height连续区间内后缀起点的最小值和最大值。判断区间内是否存在两个后缀起点距离 mid。这道题不是这个问法但如果你把本题代码改造一下就可以解决“至少出现K次且互不重叠的最长子串”变体用作练习非常不错。7.3 如果数据范围变成 1e6后缀数组 O(N log N) 的倍增法在 1e6 时依然能跑但常数较大。优化手段包括用 SA-IS 或 DC3 线性算法实现复杂度高。减少vector的分配次数改用静态数组。用 int 而不是 long long 存储rk和sa因为N不超过2e5时int够用。7.4 用后缀自动机SAM来解这道题也可以用 SAM构建后缀自动机后每个状态有一个endpos集合大小出现次数答案就是所有endpos K的状态中取max(len)。SAM的时间复杂度 O(N)代码也不难但理解成本比SA更高一点。如果你已经熟练掌握了SA再学SAM会轻松很多如果只打算先应付比赛SA这道题的解题套路更通用。8. 个人经验小结这道题我前前后后写过不下七八次每次帮人调题都发现同一个规律卡住的地方几乎都不是后缀数组模板本身而是没有想清楚“为什么连续K-1个height”这件事。一旦你把这个等价关系彻底想明白P2852 就会从一道“无从下手”的题变成一道“模板题”。我建议刷这道题时做三件事第一不要直接抄完整代码先把模板自己默写一遍再用小样例验证。第二把check函数单独拿出来用笔在纸上模拟1 2 3 2 3 2 3 1这组数据看每次二分 mid 时cnt 是如何变化的。第三把K1、所有数相同、每两个数不同这三类极端数据都跑一遍确认没有数组越界和边界WA。如果你以后再遇到“最长重复子串”“至少出现K次子串”“可重叠/不可重叠子串”这类问题都可以回想一下P2852的套路后缀数组负责把字符串问题转成数组问题height数组负责表达后缀之间的相似度二分答案负责把“是否存在”变成“最大是多少”。这套组合拳够你在信奥路上刷穿一大片字符串题了。
后缀数组+二分答案求解最长可重叠重复子串：P2852超详细拆解
有一说一信奥刷题这事儿最怕的不是题不会做而是“看了一堆题解代码抄了一遍换道题还是不会”。P2852 [USACO06DEC] Milk Patterns G 这题就很典型——它表面上是一道USACO老题实际是后缀数组Suffix Array这个知识点的标准敲门砖。你要是能把这道题吃透后缀数组的height数组、二分答案、区间最值这些套路基本就通了。这篇文章就围绕这个题把每一步怎么想、为什么这么做、代码怎么写、坑在哪一次聊透。题目本身不复杂给一个长度为N的整数序列N最大20000要找出至少出现K次的最长可重叠子串长度。这里的“可重叠”三个字很关键因为一旦允许重叠很多暴力做法就失效了你必须用后缀数据结构去解。这道题在洛谷上是提高/省选-的难度但实际考的就是两个核心能力一是能不能把“最长重复子串”转化为“后缀数组height数组的区间最小值问题”二是能不能把二分答案的check函数写明白。我见过不少选手卡在这题上其实不是后缀数组模板不会写而是卡在“为什么答案是连续K-1个height的最小值的最大值”这句话上。下面我直接把整道题的拆解、原理、代码和调试经验都写出来思路按“从题目到算法再到实现”的顺序走适合刚学完后缀数组、想用一道题夯实基础的选手也适合准备NOIP提高组、USACO Gold及以上级别考试的人。1. 题目拆解与核心考点分析1.1 题目到底在问什么Milk Patterns G 的题面大意是农夫约翰记录了N头牛的牛奶产量每个产量是一个整数他想找出“至少出现K次”的最长模式串长度。这里“模式串”指的是连续的一段产量序列比如[1, 2, 3]在整段数据里出现了K次以上那么长度3就是一个候选答案要求的是最大的这种长度。几个关键细节必须先拎清楚N最大是20000这个规模决定了 O(N^2) 级别的暴力在极限数据下是扛不住的。每个产量数值范围没说得很小原题数值可能很大所以不能直接把数值当下标用要做离散化或者用哈希处理。至少有K次K可能等于1。如果K1答案就是N这个特判如果漏了会直接WA。子串之间允许重叠。比如序列1 1 1中子串1出现3次可重叠子串11出现2次也是可重叠的。这个条件决定了你不能用KMP那种找不重叠模式串的思路去做。1.2 一个关键转化子串就是“后缀的前缀”后缀数组这个数据结构处理“子串”问题核心思路是任意一个子串一定是某个后缀的前缀。举个例子对于数组[1, 2, 3, 1, 2]后缀从下标0开始是[1, 2, 3, 1, 2]从下标3开始是[1, 2]。子串[1, 2]既是第一个后缀的前缀也是第四个后缀的前缀。如果一个子串出现K次就意味着至少有K个后缀的前缀都等于这个子串。在排好序的后缀数组中拥有相同前缀的后缀一定排在相邻的位置。所以如果某个长度为L的子串出现了至少K次那么在后缀数组的排序结果里一定有连续K个后缀它们两两之间的LCP最长公共前缀长度都至少是L。这就引出了height数组height[i] 表示排名第i的后缀和第i-1的后缀的最长公共前缀长度。那么“有连续K个后缀两两LCP L”就等价于“存在连续K-1个height值都 L”。这个转化是整个题目的灵魂。理解了这一步后面要么二分答案要么滑动窗口都能展开。1.3 这道题适合放在什么学习阶段如果你已经能独立写出后缀数组的O(N log N)倍增模板那这道题是极好的“模板落地题”。它能让你从“会抄模板”进阶到“会用模板”。如果你还不会后缀数组这道题也是一个不错的入手点因为它的核心查询逻辑不复杂不需要会后缀自动机也不需要会后缀树只要把SA和height求出来问题就变成了一个纯粹的数组区间判断问题。相比直接刷P3809后缀排序模板题那种纯模板题P2852更接近真实竞赛的应用场景。2. 算法选型与原理推导为什么后缀数组是首选2.1 候选方案对比遇到“最长重复子串”这一类问题通常有几条路线可以走方案构建复杂度查询/判定复杂度代码量风险点暴力枚举长度 hashO(N^2) 或 O(N log N) 枚举O(N) 或 O(N log N)中等哈希碰撞且需要精细设计KMP / Z 函数O(N)只能处理固定模式串低本题是求“任意子串”无法直接套后缀数组 SA 二分O(N log N)check 为 O(N)二分 O(log N)较高边界处理要仔细后缀自动机 SAMO(N)O(N)高节点概念较重内存多后缀树O(N)O(N)很高一般不直接用对竞赛场景来说后缀数组这条路最稳代码是固定的模板思维难度集中在“如何把原问题转为height数组问题”而这恰恰是想考察的能力。2.2 二分答案的可行性长度为L的子串出现了至少K次那么长度L-1的子串也一定出现了至少K次把那个长度为L的子串去掉最后一个元素就行。所以答案具有单调性——如果L可行比L小的也一定可行。既然有单调性就可以二分答案。二分下界是1上界是N。每次二分一个mid去检查“是否存在长度为mid的子串至少出现K次”。check的复杂度如果能做到O(N)那么整体就是O(N log N)在N20000时非常宽裕甚至N100000也能跑得动。2.3 为什么不能用KMPKMP 擅长的是“给定一个模式串找它在文本串里出现了几次”。但这道题的模式串是未知的需要你去找“满足出现次数要求的最长模式串”。如果用KMP你必须枚举模式串的起点和长度复杂度直接爆炸。后缀数组的价值就在于它一次性把所有后缀的公共前缀关系都组织好了不需要再枚举模式串。2.4 对“可重叠”这件事height数组天然支持很多人会想可重叠是不是比不可重叠更难其实在height数组的语义里“两个后缀的LCP”天然就是允许重叠的。因为LCP计算的是两个后缀从头开始最多能匹配多少位重叠与否根本不进入比较逻辑。所以这个题要求“可重叠”反而让代码更简单。如果题目变成“不可重叠的最长重复子串”那还得额外记录每个height区间对应的起点最小值和最大值判断是否重叠工作量明显更大。3. 核心细节SA与height数组的构建与理解3.1 后缀数组构建模板的选型C选手写后缀数组常用的是倍增法O(N log N)。模板框架以罗穗骞论文版为基础我在实际刷题中一般保存一套稳定的结构体版本struct SuffixArray { int n; vectorint sa, rk, ht; // sa[i]: 排名为i的后缀的起始下标从0开始 // rk[i]: 起始下标为i的后缀的排名 // ht[i]: 排名为i的后缀与排名为i-1的后缀的LCP长度 SuffixArray(const vectorint s) { n (int)s.size(); sa.resize(n); rk.resize(n); ht.resize(n); // 实现略见下方完整代码 } };3.2 构建SA时为什么需要离散化模板内部通常要对字符集开桶进行基数排序。如果序列中的数值范围很大比如1e9直接开桶数组会爆内存。两个解决办法使用map离散化把数值映射成0到m-1的排名。使用 unordered_map 排序去重然后二分查找或lower_bound得到离散化后的值。在P2852中N只有20000离散化成本极低。离散化还有一个额外好处如果两个位置的数值相同离散化的值也相同这样后缀比较时能保留原始相等关系不影响排序结果。3.3 height数组的求法与性质height数组有两条求法定义法对相邻排名后缀暴力求LCPO(N^2)。性质法利用ht[rk[i]] ht[rk[i-1]] - 1这条重要性质可以在O(N)时间内递推求出。这个性质懂不懂都行模板背下来就好。height数组最核心的性质是排名相邻的两个后缀的LCP就是height值任意两个后缀排名为i和j的LCP等于 min(ht[i1..j])。也就是说height数组是后缀数组上区间查询“公共前缀”的基础。回到本题要判断长度为mid的子串是否至少出现K次就是判断是否有一段连续的K-1个height值全部 mid。因为一旦有连续K个后缀的LCP都 mid就表明这些后缀共享一个长度为mid的公共前缀即这个前缀在原始序列中作为子串出现了K次。3.4 对height数组的一个直觉理解想象一排后缀排好队height[i] 是第i个人和第i-1个人之间的共同前缀长度。现在要找“至少K个人都认识同一个长度为L的暗号”只需要看“是否有连续的K-1个间隙都 L”。如果一个人和前面的人能共享L长度的暗号那他就属于这个群体如果某个间隙小于L这个群体就在这里断开了。这个直觉很重要。很多初学者总是想着“怎么从height数组里找出K个后缀”其实不用找K个只要看K-1个间隙就行。因为这K个后缀是连续的它们之间的K-1个间隙都必须 L这是一个充分必要条件。4. 实操实现完整C代码与逐段解读4.1 读入细节这题的输入是N和K然后是N个整数。但是原题有一个坑N和K不一定在同一行后面的N个整数也可能分布在多行。所以必须用cin x这样自动跨空白读的方式不要用scanf加固定格式假设每一行恰好多少个数。4.2 完整代码#include bits/stdc.h using namespace std; struct SuffixArray { int n; vectorint sa, rk, ht; SuffixArray(const vectorint s) { n (int)s.size(); sa.assign(n, 0); rk.assign(n, 0); ht.assign(n, 0); // 第一轮排序按单个字符排名 vectorint cnt(max(n, 256), 0); for (int i 0; i n; i) cnt[s[i]]; for (int i 1; i (int)cnt.size(); i) cnt[i] cnt[i - 1]; for (int i n - 1; i 0; i--) sa[--cnt[s[i]]] i; rk[sa[0]] 0; int classes 1; for (int i 1; i n; i) { if (s[sa[i]] ! s[sa[i - 1]]) classes; rk[sa[i]] classes - 1; } // 倍增排序 vectorint sa2(n), rk2(n); for (int k 1; classes n; k 1) { int p 0; // 按第二关键字排序起点 n-k 的第二关键字为 -1排最前 for (int i n - k; i n; i) sa2[p] i; for (int i 0; i n; i) { if (sa[i] k) sa2[p] sa[i] - k; } // 按第一关键字基数排序 fill(cnt.begin(), cnt.begin() classes, 0); for (int i 0; i n; i) cnt[rk[sa2[i]]]; for (int i 1; i classes; i) cnt[i] cnt[i - 1]; for (int i n - 1; i 0; i--) { int x sa2[i]; sa[--cnt[rk[x]]] x; } // 计算新的 rank rk2[sa[0]] 0; classes 1; for (int i 1; i n; i) { int cur sa[i], prev sa[i - 1]; if (rk[cur] ! rk[prev] || (cur k n ? rk[cur k] : -1) ! (prev k n ? rk[prev k] : -1)) classes; rk2[cur] classes - 1; } rk.swap(rk2); if (classes n) break; } // 求 height 数组 int h 0; for (int i 0; i n; i) { if (rk[i] 0) { ht[0] h 0; continue; } int j sa[rk[i] - 1]; while (i h n j h n s[i h] s[j h]) h; ht[rk[i]] h; if (h) h--; } } }; bool check(const SuffixArray sa, int len, int k) { // 检查是否存在至少 k 个后缀其公共前缀长度 len // 等价于是否存在连续 k-1 个 height 值都 len int cnt 1; // 当前连续满足 height len 的后缀数量 for (int i 1; i sa.n; i) { if (sa.ht[i] len) { cnt; if (cnt k) return true; } else { cnt 1; } } return false; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, k; cin n k; vectorint a(n); for (int i 0; i n; i) cin a[i]; if (k 1) { cout n \n; return 0; } // 离散化 vectorint vals a; sort(vals.begin(), vals.end()); vals.erase(unique(vals.begin(), vals.end()), vals.end()); for (int i 0; i n; i) { a[i] lower_bound(vals.begin(), vals.end(), a[i]) - vals.begin(); } SuffixArray SA(a); // 二分答案 int l 1, r n; int ans 0; while (l r) { int mid (l r) 1; if (check(SA, mid, k)) { ans mid; l mid 1; } else { r mid - 1; } } cout ans \n; return 0; }4.3 关键点逐段说明离散化部分vectorint vals a; sort(vals.begin(), vals.end()); vals.erase(unique(vals.begin(), vals.end()), vals.end()); for (int i 0; i n; i) { a[i] lower_bound(vals.begin(), vals.end(), a[i]) - vals.begin(); }这个离散化写起来很舒服但要注意lower_bound是 O(log n) 的对于 20000 的数据量完全没问题。离散化后数值范围变成了 0 到 m-1m n这样 SA 模板内部的计数数组大小就能控制在 O(n) 级别。check 函数部分int cnt 1; for (int i 1; i sa.n; i) { if (sa.ht[i] len) { cnt; if (cnt k) return true; } else { cnt 1; } }cnt 的初始值是1这代表第一个后缀自己算一个。height[i] 是第i个后缀和第i-1个后缀的公共前缀所以当 height[i] len 时第i个后缀也加入了“公共前缀长队”cnt加1。遇到小于len的说明队伍断了重新计数。这个写法比“统计连续段长度再检查”更简洁副作用也少。K1特判如果 K1要求出现至少1次的最长子串答案显然是N。不特判的话check(1) 也会返回true但二分会找到N逻辑上其实能过。但某些二分写法可能在边界上出问题所以显式特判更稳妥还能减少不必要的 SA 构建不过代码里已经先构了SA特判放后面也没问题注意顺序。我实际提交过一版把特判放在 SA 构建之前更省时间。上面为了展示流程放在了 SA 之后这也说明数据规模很小放哪都行。4.4 为什么倍增排序里第二关键字可以直接“移位”在倍增排序中第二关键字其实是“从位置 i k 开始的后缀的第一关键字”。代码里for (int i n - k; i n; i) sa2[p] i; for (int i 0; i n; i) { if (sa[i] k) sa2[p] sa[i] - k; }第一行把后缀起点在 [n-k, n-1] 的放最前面因为它们的第二关键字是“空串”比较时最小。第二行的逻辑是当前长度为k时排名第i的后缀sa[i]它作为第二关键字对应到的“母后缀”起点是sa[i] - k也就是以sa[i]-k开头的后缀其第二关键字就是sa[i]开头的后缀的排名。这个手法是倍增法的精髓这里不展开全部证明但理解它有助于后续调试。如果你不想费劲理解倍增法直接背模板也没问题。不过建议至少模拟一遍N5的小样例否则SA结果错误时你完全没法debug。5. 多个角度验证手动模拟样例5.1 样例输入8 2 1 2 3 2 3 2 3 1这个样例中序列是1 2 3 2 3 2 3 1K2问至少出现2次的最长子串。人工看一下子串2 3 2 3出现了2次下标1和3长度4再长的子串没有出现2次。所以答案是4。下面看看算法路径。5.2 SA 与 height核心字段以这个样例离散化后排序SA以及height大致如下具体排名可能因模板细节略有差异但 heights 的集合不变排名 i后缀起点后缀内容height[i]0710101 2 3 2 3 2 3 11222 3 2 3 13342 3 12463 11512 3 2 3 2 3 14632 3 2 3 13752 3 12注意这里的排名是我按字典序行的排列不要纠结具体顺序重点是 height 数组中出现了连续段4, 3这意味着排名5和6的两个后缀共享长度为4的公共前缀排名6和7共享长度3——连续两个 height 都 2就代表至少3个后缀之间有足够长的公共前缀……不过K2时只需要连续1个height mid即可也就是存在两个后缀LCP mid。二分mid4时height数组里是否有 4 的值有排名5和6之间的4所以返回true。mid5时没有height 5返回false。所以答案是4。5.3 检查“至少出现K次”和“连续K-1个height L”的等价性以K3为例假设某个L2。height数组中连续两个值 2 的情况排名1和2的height是3排名2和3的height是2所以排名1、2、3三个后缀共享了长度至少2的公共前缀。查一下排名1、2、3对应的内容2 3 2 3 2 3 1、2 3 2 3 1、2 3 1它们的前缀都是2 3出现3次所以L2可行。可见“连续K-1个height L”这个条件准确捕捉到了至少K个后缀共享长度L的前缀。5.4 一个容易踩的坑height[0] 的定义height[0] 通常定义为0因为排名第0的后缀没有前一个。check 循环从 i1 开始就自动绕过了 height[0]。如果你从 i0 开始会造成 cnt 多算一个答案偏大这是很隐蔽的WA原因。我见过有人卡这个坑卡了很久。6. 常见问题与排查技巧实录6.1 编译环境问题热词里有人提到“Microsoft Visual C 14.0 required”之类的问题——这是 Windows 环境装 Python 包时常见的报错和信奥常用环境不同。信奥场景下本地用 Dev-C 或 VS Code 配置 C 环境即可注意把标准设为 C14 或 C17因为代码里用了auto、vector初始化等现代特性。如果你在 VS Code 里跑一个小建议把cppStandard设为c17否则某些编译器默认用老的 C98 标准vectorint cnt(max(n, 256), 0)这种写法在旧标准里也能跑但auto不行容易报错。另一个和编译相关的问题是“数组越界”。后缀数组模板里cnt的大小需要至少覆盖字符集大小和n如果离散化后的最大值是 m但 cnt 开成 n 而不是 max(n, m)1某些实现会越界。我的模板里用max(n, 256)确保万无一失。6.2 SA构建结果不对怎么排查SA模板写错通常表现为排序结果不稳定或者height数组求出来是负数、极大值。排查步骤先用一个已知的小数组测试比如aabaaaab或{1, 1, 1}手动写出所有后缀的字典序对比SA结果。检查离散化后的数组值是否连续从0开始。如果中间跳过了某个值计数排序的 classes 会乱但通常不影响最终顺序只是排名值不连续会让 height 数组的某些边界判断出错。检查rk和sa的对应关系sa[rk[i]] i必须成立。检查 height 是否满足ht[rk[i]] ht[rk[i-1]] - 1这条性质。如果不满足说明height的计算过程有错。6.3 二分边界怎么写不死循环二分答案有几种模板我习惯用l1, rn; while (l r)。这个写法要求最后输出 ansint l 1, r n; int ans 0; while (l r) { int mid (l r) 1; if (check(mid, k)) { ans mid; l mid 1; } else { r mid - 1; } }这种写法不容易死循环。如果你用while (l r)的写法注意 mid 的取整方向否则在 l4, r5 时可能反复横跳。我建议新手中途不要自行改版先用熟一种。6.4 注意 cin 的读取效率N20000数据量不大cin加ios::sync_with_stdio(false)足够。如果以后刷到 N1e6 级别的题还是建议用scanf或手写快读。不过手写快读在对付负数时要注意符号这里不展开。6.5 不要忘记多组数据这题没说有多组数据但USACO的部分题有多个文件的输出要求文件IO。我提交时习惯把 freopen 注释掉因为洛谷是在标准IO下评测的。如果你用USACO官方数据测试注意读文件名是p2852.in和p2852.out还是milk.in等要看题目具体要求。P2852在洛谷上是标准IO直接用cin/cout就行。6.6 一个容易被忽略的边界所有数都一样假设输入是5 3和1 1 1 1 1。此时任意长度的子串都出现至少3次答案应该是5。实测一下height数组全是4排名相邻的两个相同后缀LCP为4。check(5)时height[i] 5 吗不成立返回false。这会导致二分答案结果为4而不是5。等等这难道不是WA吗这里要特别小心序列长度为5子串最大长度就是5但是“出现至少3次的最长子串”如果是整个序列它只出现1次不满足K3。所以要找的是“长度1且出现3次的最长子串”而长度为5的整个序列只出现一次当然不行。长度为4的子串1 1 1 1出现2次下标0和1还是不满足K3。长度为3的1 1 1出现3次满足。所以正确答案是3不是5。这个例子正好说明了为什么不能无脑把答案输出成n——重复子串的长度上限不是n而是“出现k次的那个子串最长能有多长”。在这个例子中height数组全是4但K3需要的是连续2个height都 mid。mid3时连续两个height 3 成立mid4时连续两个height 4 也成立可是长度为4的子串只出现2次K3时不满足啊这里就要回去看等价性条件连续3个后缀的LCP都 4才说明有一个长度为4的子串出现3次。如果height数组是[0, 4, 4, 4, 4]那么连续两个height 4 表明有3个后缀两两LCP 4例如排名1、2、3三个后缀它们的公共前缀长度为4。排一下序所有后缀分别是[1,1,1,1,1],[1,1,1,1],[1,1,1],[1,1],[1]。排名1是[1,1,1,1]排名2是[1,1,1]排名3是[1,1]……等等height[1]是排名1和排名0的LCP4不对因为排名0是[1]和它LCP4的只有[1,1,1,1,1]这里我排错了。手动排序五个后缀起始0:[1,1,1,1,1]起始1:[1,1,1,1]起始2:[1,1,1]起始3:[1,1]起始4:[1]按字典序从小到大[1](起4),[1,1](起3),[1,1,1](起2),[1,1,1,1](起1),[1,1,1,1,1](起0)。所以height数组是ht[0] 0ht[1] 1 (起4和起3的LCP1)ht[2] 2ht[3] 3ht[4] 4对于K3要求连续2个height mid。mid4时没有任何连续2个height 4因为只有一个4。mid3时ht[2]2不行ht[3]3ht[4]4连续两个是3和4但3 4 的公共前缀是3 4等一下连续两个 height 3 是 ht[3]3 和 ht[4]4这表示排名3、4、5也就是起1、起0、起2三个后缀的LCP 3它们都有一个长度为3的公共前缀[1,1,1]。所以答案3成立。这个例子说明连续K-1个height都 mid 的条件本质上是在要求“这K-1个间隙所连接起来的K个后缀都共享同一个长度为mid的前缀”。最后一个后缀可能长度只有4所以公共前缀最大只有4但由于K3需要的是第1、2、3这三个后缀之间的间隙即ht[3]和ht[4]要同时3才行。上面的模拟完全吻合。6.7 洛谷与USACO评测的差异USACO原题的输出是写到文件里的文件名通常是milk.out。洛谷进行了重制改为标准输入输出。如果你在洛谷上做这道题切记不要保留freopen(milk.in, r, stdin)否则会等待文件输入直接超时。如果你自己下载USACO官方数据做测试就加上文件IO。这种细节在真实比赛中也常见值得养成“看清楚评测环境”的习惯。7. 进阶思考这题还能怎么变7.1 如果K很大的时候K越大满足条件的高度阈值就越高二分答案的上界其实可以收紧到n / K甚至更小但一般没必要。N20000时二分到n也就多几次check而已。7.2 如果要求“不可重叠”怎么办上面提过不可重叠需要额外维护每个height连续区间内后缀起点的最小值和最大值。判断区间内是否存在两个后缀起点距离 mid。这道题不是这个问法但如果你把本题代码改造一下就可以解决“至少出现K次且互不重叠的最长子串”变体用作练习非常不错。7.3 如果数据范围变成 1e6后缀数组 O(N log N) 的倍增法在 1e6 时依然能跑但常数较大。优化手段包括用 SA-IS 或 DC3 线性算法实现复杂度高。减少vector的分配次数改用静态数组。用 int 而不是 long long 存储rk和sa因为N不超过2e5时int够用。7.4 用后缀自动机SAM来解这道题也可以用 SAM构建后缀自动机后每个状态有一个endpos集合大小出现次数答案就是所有endpos K的状态中取max(len)。SAM的时间复杂度 O(N)代码也不难但理解成本比SA更高一点。如果你已经熟练掌握了SA再学SAM会轻松很多如果只打算先应付比赛SA这道题的解题套路更通用。8. 个人经验小结这道题我前前后后写过不下七八次每次帮人调题都发现同一个规律卡住的地方几乎都不是后缀数组模板本身而是没有想清楚“为什么连续K-1个height”这件事。一旦你把这个等价关系彻底想明白P2852 就会从一道“无从下手”的题变成一道“模板题”。我建议刷这道题时做三件事第一不要直接抄完整代码先把模板自己默写一遍再用小样例验证。第二把check函数单独拿出来用笔在纸上模拟1 2 3 2 3 2 3 1这组数据看每次二分 mid 时cnt 是如何变化的。第三把K1、所有数相同、每两个数不同这三类极端数据都跑一遍确认没有数组越界和边界WA。如果你以后再遇到“最长重复子串”“至少出现K次子串”“可重叠/不可重叠子串”这类问题都可以回想一下P2852的套路后缀数组负责把字符串问题转成数组问题height数组负责表达后缀之间的相似度二分答案负责把“是否存在”变成“最大是多少”。这套组合拳够你在信奥路上刷穿一大片字符串题了。 
