看到“奶牛矩阵”这个题名的第一反应我猜大部分人和我一样行方向跑一遍 KMP列方向再跑一遍 KMP两个循环节乘起来收工。我第一次写就是这么干的然后被一个简单样例教做人。这个题真正的难点不是 KMP 模板写不写得出来而是“最小覆盖矩阵”这个说法里有几个容易踩空的细节尤其是横向宽度这一维根本不是单独看每一行的最小周期就能拼出来的。这篇文章就把我调试了一下午之后总结出的完整思路写清楚适合卡在这个题上的同学也适合想搞明白 border 和“不完全周期”关系的读者。先说结论这道题的最优做法是“横向枚举公共周期 纵向序列 KMP”。横向部分用 KMP 的 next 数组把每一行所有可行的覆盖宽度都暴力标出来然后取所有行的交集纵向部分把一整行当成一个字符再跑一次标准 KMP。总复杂度是 O(R*C)刚好和读入字符数同级。下面拆开讲。1. 先搞清楚“最小覆盖”到底在覆盖什么1.1 覆盖条件的数学表述题目给了一个 R 行 C 列的字符矩阵要求找一个面积最小的子矩阵让它上下左右无限复制之后能把原矩阵全部覆盖。注意这里的“覆盖”允许子矩阵的边界超过原矩阵比如某一列只剩一个字符这个字符只要和子矩阵对应位置的字符相等就行并不要求宽度能整除 C。假设子矩阵的高是 h、宽是 w那么原矩阵任意位置 (i, j) 都必须满足原矩阵第 i 行、第 j 列的字符等于子矩阵第i % h行、第j % w列的字符这个式子说明了两个维度可以分开考虑横向只要保证每一个字符的下标 j 按 w 取模后依然相等纵向只要保证行下标 i 按 h 取模后整行相等。两个条件没有互相依赖所以可以分别求出最小的 h 和最小的 w最后面积就是 h * w。1.2 横向不能只对单行求最小周期最容易犯的错误是对每一行求一个 KMP 最小循环节然后对这些循环节取最小公倍数或者干脆取所有行最小循环节里最大的那个。为什么不行因为“能覆盖整行的宽度”并不是只有最小周期这一个值。比如行字符串是aabaa长度 C5。它本身的最小周期是 3因为前三个字符aab重复之后再截断成 5 个字符确实是aabaa但宽度 4 也完全可行——用aaba作为模式串复制一次之后第 5 个字符取开头第一个字符a依然对得上。所以一个行可能同时接受多个宽度只把最小周期带进计算就会漏解。横向的真正要求是对于一个宽度 w这一行的每个位置 j 都要满足s[j] s[j % w]。这个条件不要求 w 整除 C也不需要 w 是这一行的最小周期。它只要求“w 是这一行的一个可行覆盖宽度”。我们要找的是所有 R 行都同时接受的宽度里最小的那一个。2. 横向宽度border链枚举所有可行周期这才是巧妙暴力2.1 border 和可行宽度的一一对应关系KMP 的 next 数组有人习惯叫 pi 数组里存的是前缀函数也就是每个前缀的最长相等前后缀长度。一个长度 b 的 border 意味着字符串的前 b 个字符和后 b 个字符完全相等。这里有一个非常关键的转化如果字符串 S 长度为 C存在一个长度为 b 的 border那么w C - b就是一个可行覆盖宽度。原因可以这样看border 的条件是S[0..b-1] S[C-b..C-1]而C-b正好等于 w所以上面这个等式等价于“从第 w 个字符开始的那一段等于开头的那一段”。也就是说用开头 w 个字符作为模式串复制到后面是能匹配上的。对于更靠后的位置只需要沿着 border 链继续把这种关系传递下去所以任意一个 border 长度 b 都对应一个可行的 w。这就是为什么我们不能只看最大的 border。最大 border 只能给出最小的周期C - pi[C-1]但多行公共宽度可能落在其他 border 对应的宽度上。例如aabaa的 border 链是 2 - 1 - 0对应的可行宽度就是 3、4、5其中 4 这个宽度只靠最大 border 是看不出来的。2.2 用 next 链把一行的可行宽度全部标出来对一个字符串 S先正常求出它的 next 数组。然后用一个游标 j 从next[C-1]开始沿着j next[j-1]一路往下走直到 j 变成 0j next[C-1] while (j 0) { w C - j // 这个 w 是本行的可行宽度 标记 w j next[j-1] // 跳到下一个更短的 border } // j 0 时w C整行本身当然可行也要标记 标记 w C每跳一次j 都会严格变小所以每一行标记的宽度数量不会超过 C。虽然一行里可能标记出很多宽度但所有行加在一起的总标记次数不会超过 R * C也就是和输入字符数同级。这也就是标题里“巧妙暴力”的由来理论上最坏是 O(RCC)但用 border 链压缩之后我们把每一行真正需要关注的候选宽度压缩到了 O(C) 个。2.3 多行取交集的实现细节有了每一行的可行宽度集合之后剩下的问题就是取交集。我用两个数组cnt[w]统计有多少行认为宽度 w 可行last[w]记录宽度 w 最后一次是被第几行标记的用来防止同一行重复计数。处理每一行的时候如果当前行要标记宽度 w先看last[w]是不是等于当前行号。不是才把cnt[w]加一然后更新last[w]。虽然 border 链不会产生重复宽度但写上这个判断能避免以后改代码时踩坑成本也几乎为零。最后从 1 开始枚举宽度找到第一个cnt[w] R的 w这就是所有行都接受的最小宽度。这里要注意宽度 C 也就是整行本身对任何一行都是可行的所以最后一定能找到答案不会出现无解的情况。3. 纵向高度把整行当字符再跑一次 KMP3.1 行序列的 KMP 和普通 KMP 只有一个区别横向问题解决之后纵向就简单了。现在矩阵可以看成是一个长度为 R 的序列序列里的每个元素是一整行字符串。我们要找最小的 h使得“前 h 行的整体”循环重复之后能覆盖整个行序列。这本质上就是对一个“字符”比较规则不同的字符串做 KMP。普通 KMP 比较两个字符用char char这里比较两个元素用string string。代码上就是把比较函数从字符相等改成整行相等其他逻辑完全一样。于是我可以先对行序列求一个前缀函数piRfor (int i 1; i R; i) { int j piR[i-1]; while (j 0 grid[i] ! grid[j]) j piR[j-1]; if (grid[i] grid[j]) j; piR[i] j; }之后最大 border 就是piR[R-1]最小高度就是h R - piR[R-1]如果 R1piR[0]0h1也没问题。3.2 为什么纵向不需要枚举 border 链横向需要对每一行枚举所有 border是因为那是多个字符串之间找公共可行宽度。而纵向现在只有一个序列只需要找到这个序列自己的最小可行周期直接用最大 border 就够了。道理很简单可行高度 h 越小对应的 border 长度R - h就越大。最小的可行高度一定对应最大的 border也就是 KMP 前缀函数算出来的最后一个值。所以纵向不需要再像横向那样维护cnt数组直接一个减法就出来。3.3 一个容易忽略的细节必须比较整行这个细节我第一次写的时候就漏了。纵向 KMP 比较两个“元素”的时候必须把整行字符串完整地参与比较不能只比较前 w 个字符。如果只比较前 w 个字符纵向可能得到一个更小的 h但这个 h 只保证了每一行的开头的 w 列能对上。一旦复制出来的部分覆盖到第 w 列之后后面那些列会因为行和行之间不同而崩掉。行覆盖解决的是纵向重复列覆盖解决的是横向重复两者是配合关系不能把某个维度的比较范围提前缩减。所以稳妥的做法就是直接用vectorstring存矩阵KMP 比较时用。在 R * C 不超过 1e6 的数据范围下这个开销完全可以接受。4. 完整代码与复杂度分析4.1 参考实现下面是完整的 C 代码横向枚举 border 链纵向跑序列 KMP最后输出h * w。#include bits/stdc.h using namespace std; vectorint get_pi(const string s) { int n (int)s.size(); vectorint pi(n, 0); for (int i 1; i n; i) { int j pi[i - 1]; while (j 0 s[i] ! s[j]) j pi[j - 1]; if (s[i] s[j]) j; pi[i] j; } return pi; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int R, C; if (!(cin R C)) return 0; vectorstring grid(R); for (int i 0; i R; i) { cin grid[i]; } // 横向找出所有行都接受的公共最小宽度 vectorint cnt(C 1, 0), last(C 1, -1); for (int i 0; i R; i) { vectorint pi get_pi(grid[i]); int j pi[C - 1]; while (j 0) { int w C - j; if (last[w] ! i) { last[w] i; cnt[w]; } j pi[j - 1]; } // 整行本身一定是可行的 if (last[C] ! i) { last[C] i; cnt[C]; } } int w 1; while (cnt[w] ! R) w; // 纵向把每一行当成一个字符跑序列 KMP vectorint piR(R, 0); for (int i 1; i R; i) { int j piR[i - 1]; while (j 0 grid[i] ! grid[j]) j piR[j - 1]; if (grid[i] grid[j]) j; piR[i] j; } int h R - piR[R - 1]; cout h * w \n; return 0; }4.2 复杂度为什么是 O(R*C)横向每一行要做的操作包括求该行的 next 数组O(C)沿 border 链标记宽度border 链长度不超过 C均摊 O(C)。R 行都做一遍总操作量是 R * C正好等于输入字符数。最后找最小公共宽度时枚举 C 个位置也包含在这个量级里。纵向序列 KMP 的循环次数是 O(R)但每次grid[i] ! grid[j]比较字符串可能付出 O(C) 的代价。最坏情况下所有行都相等比较会走完整行总数也是 R * C。如果 R 和 C 的乘积在 1e6 以内这个复杂度非常安全。5. 踩坑记录和几个值得注意的边界5.1 关于“每行最小周期取 LCM”的讨论网上不少题解是这么写的先对每一行用 KMP 求出最小循环节然后对所有行的最小循环节取最小公倍数如果最小公倍数大于 C 就取 C。这个做法在 POJ 的老数据里也许能过但并不是严谨的算法。问题出在“一行可行宽度”不止最小周期一个。比如aabaa这个字符串最小周期是 3但它真实的可行宽度还有 4 和 5。如果另一行刚好接受 4 而不接受 3那么 LCM 方法会错过 4 这个更优的公共宽度。想要稳过加强数据老老实实把所有 border 对应的宽度都枚举出来取集合交集才是正解。说白了KMP 的 next 数组并不只是用来求单一字符串的最小循环节的它把字符串所有的周期关系都编码在了 border 链里。这个题的横向部分考的就是你对这个链的理解。5.2 几个容易写错的细节第一下标一定要分清楚。横向 KMP 是 0-indexed所以最大 border 在pi[C-1]跳链的时候是j pi[j-1]不是j pi[j]。我第一次写的时候写成了后者直接死循环。第二cnt[w] R的判断不能写成cnt[w] R。虽然加了last判断之后cnt[w]不会超过 R但写成能让你更清楚地意识到这个数组的语义是“有多少行支持这个宽度”。第三如果矩阵只有一行或者一列代码要能正常跑。C1 时横向标记只需要标记宽度 1R1 时纵向 h 1面积就是这一行的最小覆盖宽度。5.3 我自己验证代码的小方法写完代码之后最好先写一个暴力对拍程序验证横向部分。暴力做法很简单枚举 w 从 1 到 C依次检查每一行是不是满足s[j] s[j % w]。数据规模小的时候完全可行。我自己的习惯是用随机字符矩阵跑几千组把暴力求出的最小面积和 KMP 优化后的答案对拍。这样能快速暴露你对“border 链宽度”的理解是否有偏差。如果对拍全过再提交到 OJ 就会安心很多。另外在实际比赛里如果担心vectorstring的比较效率可以把每一行先映射成一个整数 ID然后对整数序列跑 KMP。不过需要注意哈希碰撞问题工程上可以双哈希兜底。但在 R * C 只有 1e6 的题目限制下直接比较字符串已经完全够用没必要提前优化到那种程度。这道题做完之后我的直观感受是KMP 这个算法本身不难写难的是想清楚它给的 next 数组里到底藏着哪些信息。奶牛矩阵的横向枚举就是把“所有可行周期”这个平时容易忽略的概念挖了出来。搞懂这一次之后以后再遇到二维覆盖、多串公共周期这类问题思路会顺很多。
