先说结论这道题真正考的不是二维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的串循环生成。行和列之间没有耦合关系因为平铺是横竖两个方向的笛卡尔积横向周期和纵向周期互不影响。所以整道题的解题路径就非常清晰了求出最小的合法宽度 W求出最小的合法高度 H答案就是 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%31根本除不尽但完全不影响它作为周期来覆盖。这里我强烈建议你把求最小周期单独封装成一个函数不要去套KMP匹配模板。KMP匹配模板里有很多j回溯逻辑而这里只需要一次next数组扫描非常简单也不容易写错。2.2 为什么 p n - next[n-1] 总是对的直观理解是这样next[n-1] k 表示字符串最后一个字符能和开头的第k个字符对上也就是说整个字符串的后k个字符和前k个字符完全相等。既然首尾重叠了k个字符那么从第k1个字符开始就是在重复前面部分的节奏。于是从第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。如果按某些博客说的“取所有行最小周期的最大值”你会得到宽度W3。用宽度3的子矩阵去覆盖第二行没问题但回到第一行试试第一行前3个字符是“aba”把“aba”重复展开成“abaabaaba...”第4个字符是a而原矩阵第一行第4个字符是b当场就覆盖失败。正确做法是求最小公倍数lcm(2,3)6W6。也就是说这种情况下只能把整个行宽都当作子矩阵宽度。所以这里的“取最大值”是个经典误区。为什么因为要让一个宽度W同时成为多行字符串的周期W必须同时属于每行的周期集合。如果第一行的最小周期是2那么它的合法周期就是2的倍数2、4、6……如果第二行的最小周期是3合法周期是3、6、9……两边交集的最小值就是6。这个交集本质就是最小公倍数。3.2 合并过程中的边界处理代码里合并LCM时有一个必须处理的细节如果累积LCM已经超过了矩阵总列数M那就不需要再算了直接把W置成M。因为宽度超过M的子矩阵一定大于等于原始行宽用它去覆盖一整行时第一块瓷砖就已经把整行包含进去了因此必然是合法宽度。但面积不可能是最优的因为WM意味着这一维上没有任何压缩空间不过至少结果是对的。如果只用单精度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 主函数结构与计算框架整个实现的骨架很简单读入n和m读入n行字符串对每一行调用getMinPeriod得到p_i逐个并入LCM得到W把矩阵转置对每一列调用getMinPeriod得到q_j逐个并入LCM得到H输出W*H。第3步的转置可以选择真正开一个新数组也可以直接在原矩阵上按列构造字符串。考虑到题目数据只有2000行2000列直接构造转置矩阵没有任何压力代码反而更清晰。4.2 getMinPeriod函数的写法vectorint buildNext(const string s) { int n (int)s.size(); vectorint 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; vectorint ne buildNext(s); return n - ne[n - 1]; }这里有一个容易写错的细节buildNext里j的初始值是ne[i-1]而不是每次重新从0开始。如果你照抄KMP匹配里的写法很容易把ne数组求错。建议在本地用几个经典字符串测试一下next数组再继续。4.3 转置矩阵vectorstring transpose(const vectorstring a, int n, int m) { vectorstring 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; vectorstring 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; } } vectorstring 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第二行、第三行也都是1LCM算下来width1。转置后每一列都是“aaa”最小周期也是1height1。答案就是1。这个结果符合直觉一个字符的瓷砖平铺出来当然能覆盖整张全a矩阵。5.2 行周期不同但列周期完全一致输入2 6 ababab abcabc刚才已经算过第一行最小周期2第二行最小周期3widthlcm(2,3)6。再看列每列长度2第一列“aa”最小周期1第二列“bb”也是1第三列“ac”最小周期2第四列“ba”也是2第五列“ab”是2第六列“bc”是2。列方向所有最小周期的LCMlcm(1,1,2,2,2,2)2所以height2。最终答案是12也就是把整个2×6矩阵当作唯一的重复块。这个过程能跑通说明两个方向是独立的也能验证“取最大值”思路在这个数据上确实会出错。5.3 单行矩阵输入1 5 abcab单行的话宽度其实就是这一行的最小周期getMinPeriod返回5-23。转置后变成5行1列的矩阵每一列都是单个字符height1。答案是3×13也就是取“abc”这个1×3子矩阵平铺后能覆盖“abcab”。读者可以自己手推一下“abc”重复展开成“abcabc...”前5个字符确实是“abcab”正确。5.4 单列矩阵输入5 1 a b x b a列方向的字符串是“abxba”对称结构长度5next[4]1因为首尾都是a最小周期p4。但这里width1因为只有一列。答案是4×14。用高度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 常见问题速查表症状可能原因解决办法答案只比正确答案大一点给最小周期加了整除判断去掉n % p 0的条件答案明显偏大尤其是全相同矩阵每行循环节算错检查next数组起始下标某几组数据溢出为负数LCM合并溢出使用long long超宽直接置为m/n转置后结果不对转置矩阵下标写反用n*m维的小数据打印转置结果核对暴力枚举能过但KMP版本过不了公共周期不是最大值而是LCM改用LCM合并再取min(m/n)最后说一个实战体会我第一次写这道题时把大量时间花在研究和实现“二维KMP”上最终得到一堆看不懂的代码提交也是错的。后来换成本文这种“暴力枚举验证 KMP求周期 LCM合并”的思路整份代码不到100行调试只花了几分钟。竞赛题里很多所谓的“二维”问题本质都是可以拆成一维的关键是你敢不敢先把暴力的判定规则写清楚再让KMP去加速。这道题最大的收获不是记住了LCM公式而是学会了“先暴力想清楚合法性再用算法优化”的做题节奏。希望这篇文章能帮你少走我当时走过的弯路。