二维矩阵最小覆盖子矩阵：KMP求周期与LCM合并的巧妙解法

先说结论：这道题真正考的不是二维KMP，而是“能不能把二维平铺问题拆成一维周期问题”的抽象能力。我最初拿到“奶牛矩阵 / Milking Grid”这个题目时，第一反应是去找二维KMP模板，结果整个思路被带偏了。后来冷静下来把题意转换成“瓷砖平铺”模型，发现只需要把每一行、每一列分别交给KMP求周期，再做一个“看似暴力、其实极其巧妙的LCM合并”就能完全解决。这篇文章就把我完整踩过的路、趟过的坑，以及最终那份可以直接提交的C++代码一起放出来。

这道题在某个算法OJ上的编号是159，输入是一个 N 行 M 列的字符矩阵，只由小写字母组成。要求找一个面积最小的子矩阵，让这个子矩阵在行、列两个方向上无限重复（允许超出边界）后，能够覆盖住原矩阵的所有格子。适合已经会一维KMP、想进阶二维字符串问题的选手参考。如果你还不太熟悉KMP，我会把next数组和最小周期的关系也一起捋一遍，保证看完能上手写代码。

1. 题干拆解：先弄明白“覆盖”到底是什么意思

1.1 原题到底要我们算什么

给定一个 N×M 的小写字母矩阵，要找出一个面积最小的子矩阵。所谓“覆盖”，不是让你把原矩阵严格切成若干个整数个子矩阵，而是允许铺出来的瓷砖在右边界和下边界被“截断”。打个比方：你用一块带花纹的瓷砖从左上角开始铺地面，铺到墙根时最后一块往往需要裁掉一截，但花纹仍然能对上。题目要求的就是：找到面积最小的那种“瓷砖”，使得无论铺多远，原矩阵永远都是这块瓷砖重复后的左上角那一片。

输入的行数、列数上限印象里是2000左右，所以O(N^2 M^2)这类枚举子矩阵再暴力验证的方案基本就别想了。但只要抓住“周期”这个数学本质，复杂度可以降到O(NM)。

这里有个很容易踩的坑：很多人把“覆盖”理解成“必须由整数个子矩阵无缝拼接”，导致去求严格整除的循环节。如果真是那样，样例里很多答案是错的。题目说的是重复平铺，允许最后一截不完整，所以只要满足“每一位字符都等于以某个宽度为周期推出来的字符”即可，并不要求总长度能整除周期长度。

1.2 把二维问题压成一维

既然允许平铺，那么子矩阵的宽度W是否合法，只取决于每一行字符串是否都能由长度为W的串循环生成。同理，子矩阵的高度H是否合法，只取决于每一列字符串是否都能由长度为H的串循环生成。行和列之间没有耦合关系，因为平铺是横竖两个方向的笛卡尔积：横向周期和纵向周期互不影响。

所以整道题的解题路径就非常清晰了：

1. 求出最小的合法宽度 W；
2. 求出最小的合法高度 H；
3. 答案就是 W * H。

“先求宽再求高”这个顺序看起来很普通，但很多人在第一步就翻车了。原因是他们只对“行”做KMP，然后天真地把每行的最小周期长度取最大值当作W，这一步是错的，我后面会专门用反例说明。

2. KMP与最小周期的关系

2.1 next数组的另一种用法

KMP的next数组（有些地方叫fail数组或失配数组）通常用来做字符串匹配，但在这种题里，它还有一个冷门但极其有用的性质：一个字符串的长度为n，它的“最小周期”长度 p = n - next[n]。

等等，这里的next[n]是指什么？如果题目模板里next数组长度是n，下标从0到n-1，那么就是 n - next[n-1]。这个式子对任意字符串都成立，你不需要验证它是否整除n。因为在平铺覆盖的语义下，周期长度本来就不要求整除字符串长度。

举个例子，看字符串：

abcab

长度5，它的next数组最后一个值是2，因为真前缀“ab”和真后缀“ab”相等，长度为2。于是最小周期 p = 5 - 2 = 3。这意味着用宽度为3的模式串“abc”无限重复，得到“abcabcabc...”，截取前5个，正好是“abcab”。你看，5%3=1，根本除不尽，但完全不影响它作为周期来覆盖。

这里我强烈建议你把求最小周期单独封装成一个函数，不要去套KMP匹配模板。KMP匹配模板里有很多j回溯逻辑，而这里只需要一次next数组扫描，非常简单，也不容易写错。

2.2 为什么 p = n - next[n-1] 总是对的

直观理解是这样：next[n-1] = k 表示字符串最后一个字符能和开头的第k个字符对上，也就是说整个字符串的后k个字符和前k个字符完全相等。既然首尾重叠了k个字符，那么从第k+1个字符开始，就是在重复前面部分的节奏。于是从第p个字符开始继续往后循环，正好能接上。

严谨的证明在字符串周期引理里讲得很透，这里只说竞赛视角：KMP求出的next数组，本质上是找“自身匹配自身”的最大前缀后缀交叠长度。周期长度就是去重覆盖后剩下的那一截，所以这个式子对任意串都成立。如果你正在看某个字符串题解，发现别人用“最小循环节 = n - next[n-1]，并且要求n % (n - next[n-1]) == 0”，你就要多留个心眼：这种写法只能处理整除的情况，在本题这种允许截断平铺的模型下是判错数据的。

3. 多行周期合并：为什么是LCM而不是最大值

3.1 一个能击穿“取最大值”的反例

假设矩阵有2行6列：

ababab abcabc

第一行“ababab”的最小周期是2，第二行“abcabc”的最小周期是3。如果按某些博客说的“取所有行最小周期的最大值”，你会得到宽度W=3。用宽度3的子矩阵去覆盖第二行没问题，但回到第一行试试：第一行前3个字符是“aba”，把“aba”重复展开成“abaabaaba...”，第4个字符是a，而原矩阵第一行第4个字符是b，当场就覆盖失败。

正确做法是求最小公倍数：lcm(2,3)=6，W=6。也就是说，这种情况下只能把整个行宽都当作子矩阵宽度。所以这里的“取最大值”是个经典误区。

为什么？因为要让一个宽度W同时成为多行字符串的周期，W必须同时属于每行的周期集合。如果第一行的最小周期是2，那么它的合法周期就是2的倍数：2、4、6……如果第二行的最小周期是3，合法周期是3、6、9……两边交集的最小值就是6。这个交集，本质就是最小公倍数。

3.2 合并过程中的边界处理

代码里合并LCM时，有一个必须处理的细节：如果累积LCM已经超过了矩阵总列数M，那就不需要再算了，直接把W置成M。因为宽度超过M的子矩阵，一定大于等于原始行宽，用它去覆盖一整行时，第一块瓷砖就已经把整行包含进去了，因此必然是合法宽度。但面积不可能是最优的，因为W=M意味着这一维上没有任何压缩空间，不过至少结果是对的。

如果只用单精度int来存LCM，累乘过程中很容易溢出，尤其N和M都到2000的时候。使用 long long，并且在累加过程中一旦发现超过M就提前break，不但能防溢出，还能顺手省几次无意义的计算。

3.3 如果实在理解不了LCM，你还可以暴力验证

我在纸上推导时有个习惯：先用暴力枚举验证数学结论，再写优化过的代码。这里的暴力版本很好理解：

for (int w = 1; w <= m; ++w) { bool ok = true; for (int i = 0; i < n; ++i) { for (int j = w; j < m; ++j) { if (mat[i][j] != mat[i][j - w]) { ok = false; break; } } if (!ok) break; } if (ok) { width = w; break; } }

这段代码的含义是：枚举宽度w，检查每一行从第w列开始的每个字符，是否和它左边距离w的那个字符相等。如果所有行都满足，说明w是每一行的公共周期。这是完全正确的判定方法，唯一的缺点是复杂度高，最坏O(MNM)。但我强烈建议你在学这道题的时候，先跑通这个暴力版本，再切到LCM版本。你会发现两者输出完全一致，同时你对“公共周期为什么是LCM”的理解会比只看题解深刻得多。

4. 完整实现：先横向LCM，再转置求纵向

4.1 主函数结构与计算框架

整个实现的骨架很简单：

1. 读入n和m，读入n行字符串；
2. 对每一行调用getMinPeriod，得到p_i，逐个并入LCM，得到W；
3. 把矩阵转置；
4. 对每一列调用getMinPeriod，得到q_j，逐个并入LCM，得到H；
5. 输出W*H。

第3步的转置可以选择真正开一个新数组，也可以直接在原矩阵上按列构造字符串。考虑到题目数据只有2000行2000列，直接构造转置矩阵没有任何压力，代码反而更清晰。

4.2 getMinPeriod函数的写法

vector<int> buildNext(const string& s) { int n = (int)s.size(); vector<int> ne(n, 0); for (int i = 1; i < n; ++i) { int j = ne[i - 1]; while (j > 0 && s[i] != s[j]) { j = ne[j - 1]; } if (s[i] == s[j]) ++j; ne[i] = j; } return ne; } int getMinPeriod(const string& s) { int n = (int)s.size(); if (n == 0) return 0; vector<int> ne = buildNext(s); return n - ne[n - 1]; }

这里有一个容易写错的细节：buildNext里，j的初始值是ne[i-1]，而不是每次重新从0开始。如果你照抄KMP匹配里的写法，很容易把ne数组求错。建议在本地用几个经典字符串测试一下next数组再继续。

4.3 转置矩阵

vector<string> transpose(const vector<string>& a, int n, int m) { vector<string> b(m, string(n, ' ')); for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { b[j][i] = a[i][j]; } } return b; }

转置之后，原来的每一列就变成了b里的每一行，所以可以复用一模一样的最小周期函数。我最初写的时候还在想“要不要给列单独写个逻辑”，后来发现转置才是最优解，一行都不需要复制。

4.4 LCM合并与主逻辑

#include <bits/stdc++.h> using namespace std; long long gcdLL(long long a, long long b) { return b == 0 ? a : gcdLL(b, a % b); } long long lcmLL(long long a, long long b) { return a / gcdLL(a, b) * b; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; vector<string> mat(n); for (int i = 0; i < n; ++i) cin >> mat[i]; long long width = 1; for (int i = 0; i < n; ++i) { int p = getMinPeriod(mat[i]); width = lcmLL(width, p); if (width > m) { width = m; break; } } vector<string> colMat = transpose(mat, n, m); long long height = 1; for (int j = 0; j < m; ++j) { int p = getMinPeriod(colMat[j]); height = lcmLL(height, p); if (height > n) { height = n; break; } } cout << width * height << '\n'; return 0; }

这段代码在数据范围2000以内跑得飞快，主要时间和空间都花在读入和转置上，KMP本身的复杂度只有O(NM)。如果你把getMinPeriod和transpose写好，主逻辑就只剩下一层循环加一个LCM合并，这就是题目所说的“巧妙暴力”：思路直白，实现轻松，但每一步背后都有KMP和周期理论支持。

5. 边界正确性与多组数据验证

5.1 全相同字符矩阵

输入：

3 4 aaaa aaaa aaaa

第一行的最小周期是1，第二行、第三行也都是1，LCM算下来width=1。转置后每一列都是“aaa”，最小周期也是1，height=1。答案就是1。这个结果符合直觉：一个字符的瓷砖，平铺出来当然能覆盖整张全a矩阵。

5.2 行周期不同但列周期完全一致

输入：

2 6 ababab abcabc

刚才已经算过，第一行最小周期2，第二行最小周期3，width=lcm(2,3)=6。再看列：每列长度2，第一列“aa”最小周期1，第二列“bb”也是1，第三列“ac”最小周期2，第四列“ba”也是2，第五列“ab”是2，第六列“bc”是2。列方向所有最小周期的LCM=lcm(1,1,2,2,2,2)=2，所以height=2。最终答案是12，也就是把整个2×6矩阵当作唯一的重复块。这个过程能跑通，说明两个方向是独立的，也能验证“取最大值”思路在这个数据上确实会出错。

5.3 单行矩阵

输入：

1 5 abcab

单行的话，宽度其实就是这一行的最小周期，getMinPeriod返回5-2=3。转置后变成5行1列的矩阵，每一列都是单个字符，height=1。答案是3×1=3，也就是取“abc”这个1×3子矩阵平铺后，能覆盖“abcab”。读者可以自己手推一下，“abc”重复展开成“abcabc...”，前5个字符确实是“abcab”，正确。

5.4 单列矩阵

输入：

5 1 a b x b a

列方向的字符串是“abxba”，对称结构，长度5，next[4]=1（因为首尾都是a），最小周期p=4。但这里width=1，因为只有一列。答案是4×1=4。用高度4的瓷砖去重复，比如“abxb”重复展开成“abxbabxb...”，前5个是“abxba”，能和原列完全对齐。

这些边界样例全部通过，说明算法在“宽度超过总宽度”“高度超过总高度”“不整除”这些情况下都处理得没问题。你本地测试时，建议至少把这四组数据都跑一遍，能帮你发现代码有没有把LCM写成最大值、有没有漏掉转置。

6. 常见问题与实战排坑

6.1 next数组下标起始不同导致答案错乱

竞赛里KMP模板有两种主流写法：一种下标从0开始，ne[i]表示“以i结尾的前缀”的最长相等前后缀长度；另一种从1开始，ne[i]表示“前i个字符”的最长相等前后缀长度。两者算最终周期时，一个用 n - ne[n-1]，另一个用 n - ne[n]。如果你混着用，求出来的周期可能会差一位。我的建议是固定一套写法，并且每次写完先拿“abcab”验证一下最小周期是不是3。

6.2 LCM合并没防溢出，答案变成负数

当N和M都是2000时，如果每行的最小周期都是2000以内的大质数，几个数乘起来很容易超过int范围。尤其在合并到一半还没break的时候，a / gcd(a,b) * b 在乘法那一步就可能溢出。这里除了用long long，还应该在width超过m时立即break并把width设为m，后续行已经不影响结果。高度方向同理。

6.3 把“最小周期”误写成“严格最小循环节”

很多字符串教程里会说“最小循环节必须满足 n % (n - next[n-1]) == 0”。本题的平铺允许截断，所以不能加这个整除判断。如果你加了，像“abcab”这种数据就会错误地认为最小周期是5，导致输出过大。这是一个非常隐蔽的坑，代码表面看起来没问题，结果就是有两组样例过不去。

6.4 输入行尾可能有多余空格

矩阵里只有小写字母，但某些OJ数据在行的末尾可能有多余空格。直接用cin >> mat[i]读入不会带上空格，但如果你用getline读，就要小心行尾空格导致周期判断错误。我推荐用cin逐行读字符串，不要用getline。

6.5 常见问题速查表

最后说一个实战体会：我第一次写这道题时，把大量时间花在研究和实现“二维KMP”上，最终得到一堆看不懂的代码，提交也是错的。后来换成本文这种“暴力枚举验证 + KMP求周期 + LCM合并”的思路，整份代码不到100行，调试只花了几分钟。竞赛题里很多所谓的“二维”问题，本质都是可以拆成一维的，关键是你敢不敢先把暴力的判定规则写清楚，再让KMP去加速。这道题最大的收获不是记住了LCM公式，而是学会了“先暴力想清楚合法性，再用算法优化”的做题节奏。希望这篇文章能帮你少走我当时走过的弯路。