企业官网建设流程全解析

奶牛矩阵这道题，我刷的时候第一眼是有点懵的。R 最多 10000，C 却只有 75，一个一维特别大、一个一维特别小，这种不对称的规模往往就是出题人给你的暗示。再加上“最小重复子矩阵”这种二维循环节问题，乍一看像是要枚举子矩阵再逐格验证，实际上把横向宽度枚举出来之后，纵向完全可以用 KMP 快乐收尾。这篇文章就从暴力思路讲起，把“巧妙暴力 + 快乐 KMP”这套解法拆开揉碎，适合正在准备算法比赛、或者刚学完 KMP 想找进阶应用的读者。

1. 先把题目吃透：奶牛矩阵到底要我们算什么

1.1 题目描述与本质

题目会给一个 R × C 的字符矩阵，矩阵里是小写英文字母。你要找到一个面积最小的子矩阵，使得这个子矩阵在横向和纵向不断重复平铺之后，能把原来的大矩阵完整覆盖出来。覆盖的时候允许边缘被截断，也就是说不需要大矩阵的尺寸恰好是子矩阵尺寸的整数倍。

举个例子，如果子矩阵是：

ab cd

那么平铺出来就是：

ababab... cdcdcd... ababab... cdcdcd...

如果原矩阵恰好是上面这个无限平铺的前若干行、若干列，那这个子矩阵就是合法的。题目要求在所有合法子矩阵里找出面积最小的那个，输出面积。

从数学模型上看，这就是要找两个整数 W 和 H，使得原矩阵任意位置 (i, j) 的字符满足：

mat[i][j] = mat[i % H][j % W]

这里 W 就是横向周期，H 是纵向周期。我们需要最小化 W × H。注意这里的周期是“允许截断”的弱周期，不强制要求 R 能被 H 整除、C 能被 W 整除。

1.2 一个能用手算的样例

我们构造一个简单例子来理解题目在问什么。假设原矩阵是：

abab cdcd abab cdcd

肉眼就能看出它是由 2×2 的子矩阵：

ab cd

横向重复两次、纵向重复两次得到的，所以答案是 4。但这里有一个很容易忽略的点：如果把子矩阵选成：

abab cdcd

也就是 W = 4，H = 2，面积是 8，也合法，但不是最小。如果选成 W = 2，H = 1：

ab

平铺出来每一行都变成 ababab...，但第二行应该是 cdcd，所以不合法。因此我们不能只看某一行或某一列的局部性质，横向周期和纵向周期必须同时满足整个矩阵。

1.3 “重复覆盖”的三个关键理解

第一，边缘截断不是坏事。很多人在做字符串循环节题时习惯判断“长度能否被循环节整除”，但奶牛矩阵明确允许最后一行、最后一列只覆盖一部分。这意味着我们要找的是弱周期，KMP 的 n - next[n] 公式天然支持这种截断覆盖，不需要额外判断整除。

第二，行和列是耦合的。横向周期 W 必须对每一行都成立，纵向周期 H 必须对每一列都成立。但两维又不是完全独立，因为纵向比较时需要把“每一行”当成一个整体，如果横向截断方式不同，纵向结果也会不同。

第三，目标是面积最小，不是单边最短。有可能某个 W 很小，但对应 H 很大，总面积反而不如 W 稍大、H 很小的情况。所以不能只求一个最小横向周期和一个最小纵向周期然后直接相乘，要考虑组合。

2. 为什么不能直接暴力：规模会教你做人

2.1 子矩阵枚举的复杂度爆炸

最朴素的想法是枚举子矩阵左上角坐标和宽高，然后检查它平铺后能否覆盖原矩阵。左上角有 R × C 种选择，宽高又有 R × C 种组合，直接枚举就是 O(R² × C²) 种候选。R 取 10000、C 取 75 时，这个数字是天文数字，连枚举都枚举不完。

就算我们聪明一点，固定左上角在 (0, 0)，因为平铺覆盖时子矩阵开头一定和原矩阵开头对齐，所以合法子矩阵一定是从左上角开始的。那也要枚举 O(R × C) 个宽高组合，也就是最多 10000 × 75 ≈ 75 万种。每种组合要逐格验证整个矩阵，验证一次是 O(R × C) ≈ 75 万，总复杂度是 75 万 × 75 万，完全不可接受。

2.2 二维周期检查没那么便宜

有人会说，验证一个候选子矩阵是否合法，不需要重新铺满整个矩阵吧？其实还是要逐格看。假设候选宽度是 w，高度是 h，我们得检查每个位置 (i, j) 的字符是否等于 (i % h, j % w) 的字符。即使提前 break，最坏情况仍然要遍历 R × C 个格子。

这就是二维问题的麻烦之处：一维字符串的循环节可以用 KMP 在 O(n) 时间算出来，二维矩阵如果直接做周期判断，最朴素的做法需要 O(R × C) 的时间乘上候选数量。必须先找到某种方式把二维问题降维。

2.3 规模的不对称是突破口

R 很大，C 却只有 75，这是整道题最重要的提示。如果我们把宽度 W 枚举一遍，最多只有 75 种选择。对每个 W 做一次横向合法性检查是 O(R × C)，也就是大约 75 万次字符比较，75 个 W 加起来大约 5600 万次，勉强还在可接受范围内。

真正难的是高度 H，因为 R 最大有 10000，不能直接枚举。但好消息是：一旦宽度 W 固定下来，每一行都可以用前 W 个字符唯一表示，纵向是否以 H 为周期，就变成一个长度 R 的序列的循环节问题。序列循环节正好是 KMP 的拿手好戏。这就是题目标题里“巧妙暴力”和“快乐 KMP”的分工：暴力专门对付小的 C，KMP 专门对付大的 R。

3. 快乐 KMP：一维循环节的原理和三行结论

3.1 next 数组到底在干什么

很多初学者把 KMP 理解成“字符串匹配优化工具”，这没有错，但它更底层的产品是前缀函数。对字符串 s，定义 pi[i] 为子串 s[0..i] 的最长相等前后缀长度。比如 s = "abcab"，pi[4] = 2，因为前缀 "ab" 和后缀 "ab" 相等且长度最长。

用生活类比就是：你写论文时有一段文字重复出现，但你不知道最长能重复到多长。前缀函数就是帮你找到“开头段”和“结尾段”最多能重合多少的工具。这个重合长度一旦确定，循环节长度也就跟着确定了。

3.2 最小循环节公式

对于长度为 n 的字符串，最小覆盖周期长度可以这样算：

len = n - pi[n - 1]

例如 s = "abcabcabc"，n = 9，pi[8] = 6，循环节长度就是 3。如果用长度 3 的前缀 "abc" 不断重复，恰好可以得到整个字符串。

再例如 s = "abcab"，n = 5，pi[4] = 2，得到的 len = 3。虽然 5 不能被 3 整除，但用 "abc" 重复生成 "abcabcabc..."，再截取前 5 个字符就是 "abcab"，完全能覆盖。这说明这个公式求出来的是弱周期，正好契合奶牛矩阵允许截断的设定。

3.3 为什么这个周期能覆盖到终点

这里的原理要从 border 说起。pi[n - 1] 是最长 border 长度，也就是前面 pi[n - 1] 个字符和最后 pi[n - 1] 个字符相同。把字符串想象成“前一段”和“后一段”重叠在一起，重叠长度就是 border。于是整个串可以被看成两个部分拼接，其中后半段有一部分和开头重复。

更直观的理解是：把原始字符串写成一个环，然后找旋转对称性。n - pi[n - 1] 是环上最小的移动步长，使得字符串在平移这个步长后仍然能和自身匹配。既然平移一个周期后能匹配，那么沿着这个周期一直平移下去，就能用周期前缀覆盖整个字符串，最后多出来的部分只是被截断而已。

3.4 千万别记错的 next 数组边界

很多人在模板题里用的是失配数组 next，但是在写循环节时，最好统一用前缀函数 pi。注意 pi 数组的长度和 next 数组的偏移可能不同。网上常见写法有两种：

// 前缀函数写法 vector<int> pi(m); for (int i = 1; i < m; 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; } int cycle = m - pi[m - 1];

另一种失配数组写法把 next[0] 设为 -1，循环节公式会变成 m - next[m] 之类。这两种写法很容易混，建议固定使用前缀函数，一行公式记牢：循环节 = 总长度 - 最后一个位置的 pi 值。

4. 核心思路：巧妙暴力枚举宽度 + KMP 扫高度

4.1 先想清楚一块矩阵的完整条件

假设我们确定了一个子矩阵宽度 W 和高度 H。原矩阵能由它平铺覆盖，当且仅当对任意行 i、任意列 j，都满足：

mat[i][j] = mat[i % H][j % W]

这个条件可以拆成两步理解。第一步，宽度 W 要合法，意思是对每一行来说，整行内容必须是以长度为 W 的模式重复出来的，也就是横向周期成立。第二步，在宽度 W 合法的基础上，把每一行看成一个整体，那么纵向周期 H 要合法，意思是第 i 行的内容和第 i % H 行的内容完全一致。

这里有个关键点：如果横向周期 W 成立，那么一行内容完全由它前 W 个字符决定。所以纵向比较时不需要比较整行所有字符，只需要比较前 W 个字符。

4.2 暴力枚举宽度 W：因为 C 只有 75

宽度 W 的可能取值范围是 1 到 C。我们直接枚举这个范围里的每一个 W，然后暴力检查每一行是不是以 W 为周期。检查方法非常朴素，对当前行 s，遍历每一列 j，看 s[j] 是否等于 s[j % W]。

为什么这算“巧妙暴力”？因为横向枚举只有 75 种可能，每次检查要扫 R × C 个格子，总操作量大概在 5600 万级别，这个量级在现代计算机上是可以轻松跑完的。如果不利用 C 小的特点去枚举 W，而是直接枚举 H 或者枚举子矩阵面积，那才是真正的暴力。

4.3 宽度确定后，高度就是一个一维 KMP

宽度 W 枚举完，如果它通过横向检查，我们就把每一行的前 W 个字符当作一个“字符”，得到一个长度为 R 的“字符串数组”。然后对这个数组做 KMP，求出它的最小循环节 H。

这里的处理有点抽象，我展开解释一下。假设有三行：

行0：abc 行1：def 行2：abc

如果 W = 3，那么行序列就是 ["abc", "def", "abc"]。对这个序列求循环节，发现 H = 2，因为 "abc","def" 重复后是 ["abc","def","abc","def"...]，截取前三个就得到原序列。这就意味着原矩阵以 2 为纵向周期，可以上下平铺覆盖。

用 KMP 求序列循环节时，比较两个“字符”是否相等，其实就是比较两个长度为 W 的字符串是否相等。由于 W 最大 75，这个比较代价很小。

4.4 答案取所有可行 W 中的最小面积

对于每一个通过横向检查的 W，我们都能得到一个对应的纵向最优周期 H。这个 H 是在当前 W 之下的最小纵向周期，因为 KMP 求出的循环节就是最短覆盖周期。

但注意，我们不能直接取“最小 W”对应的答案。因为面积是 W × H，有可能 W 比较小的时候 H 很大，而 W 稍微大一点的时候 H 变得很小，总面积反而更优。所以每得到一个合法的 (W, H)，就更新一次答案。

例如原矩阵只有一行，内容是 "ababab"。W = 2 时，H = 1，答案是 2；W = 3 时，横向检查会发现 "ababab" 不是以 3 为周期的吗？s[0] = 'a'，s[3] = 'b'，不相等，所以 W = 3 会被排除。最终答案就是 2。只有把所有 W 都试过，才敢确定全局最小面积。

4.5 为什么不能无脑用每行最小循环节取最大值

网上有一些流传的写法，先对每一行用 KMP 求出该行的最小循环节，然后取最大值作为 W。这个做法在部分数据下能过，但并不是严谨的做法。

举个例子，两行分别是：

ababab abcabc

第一行的最小弱周期是 2，第二行的最小弱周期是 3。如果取最大值 W = 3，横向检查第一行时，第一行变成以 "aba" 为模式重复，得到的 "abaaba" 和原串 "ababab" 并不一致，所以 W = 3 是错的。如果 W = 2，第二行同样不合法。实际上可行的最小 W 是 6，或者更准确地说，我们需要枚举而不是直接取 max 或 lcm。这道题因为 C 只有 75，枚举 W 才是既简单又正确的路。

5. 完整实现与代码精讲

5.1 C++ 代码实现

下面这份代码的思路就是先枚举宽度，再用 KMP 求高度。为了减少不必要的拷贝，我没有把每一行的前 W 个字符单独存成 string，而是在比较时直接写一个比较函数，按原矩阵的行号去逐字符比较前 W 个字符。

#include <bits/stdc++.h> using namespace std; const int MAXN = 10005; const int MAXC = 85; int R, C; string mat[MAXN]; // 比较第 a 行和第 b 行的前 w 个字符 bool rowEqual(int a, int b, int w) { for (int j = 0; j < w; j++) { if (mat[a][j] != mat[b][j]) return false; } return true; } // 检查所有行是否都以 w 为横向周期 bool checkWidth(int w) { for (int i = 0; i < R; i++) { for (int j = 0; j < C; j++) { if (mat[i][j] != mat[i][j % w]) return false; } } return true; } // 对行序列求最小纵向循环节，序列中每个“字符”是前 w 个字符 int getHeight(int w) { vector<int> pi(R, 0); for (int i = 1; i < R; i++) { int j = pi[i - 1]; while (j > 0 && !rowEqual(i, j, w)) { j = pi[j - 1]; } if (rowEqual(i, j, w)) { j++; } pi[i] = j; } return R - pi[R - 1]; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> R >> C; for (int i = 0; i < R; i++) { cin >> mat[i]; } int ans = R * C; // 初始化为最大面积 for (int w = 1; w <= C; w++) { if (!checkWidth(w)) continue; int h = getHeight(w); ans = min(ans, w * h); } cout << ans << endl; return 0; }

这份代码在思路正确的前提下，优先保证了可读性。R 最大 10000、C 最大 75，最坏情况下枚举 75 个宽度，每个宽度做横向检查大约 75 万次字符比较，再做一次 KMP 高度计算，同样大约 75 万次字符比较，总字符比较量在 1 亿上下。这个量级在 C++ 里只需要一两秒，足够通过。

5.2 关键比较函数的细节

rowEqual 函数是整份代码的心跳。它在 KMP 里被反复调用，每次最多比较 w 个字符。这个函数有一个隐藏好处：它只比较前 w 个字符，而不是整行。因为 checkWidth 已经保证了每一行可以由前 w 个字符重复生成，所以纵向比较时只需要看前 w 个字符，不用管后面的部分。

注意一个容易写错的点：在 KMP 的 while 循环里，每次失配后 j = pi[j - 1]，这个 j - 1 是下标索引，不是长度。做过 KMP 的读者应该很熟悉，但如果你习惯用 next 数组的第一种写法，这里很容易把 pi 数组的索引和比较的位置搞混。

5.3 时间复杂度与空间分析

横向检查的复杂度是：

O(C × R × C) = 75 × 10000 × 75 ≈ 5600 万

纵向 KMP 的复杂度是：

O(C × R × w) = 75 × 10000 × 75 ≈ 5600 万

两者加在一起大约 1.1 亿次字符比较，还包括 KMP 本身的指针移动，但整体开销可控。空间上只需要存 R 个字符串，每个字符串长度 C，大约 75 万个字符，非常小。前缀函数数组长度 R，也就 10000 个 int。

5.4 为什么不直接对整行做字符串哈希

其实也可以。如果把每一行的前 w 个字符计算成一个哈希值，那么 KMP 里比较两个“字符”就变成比较两个整数，速度会更快。但代价是要为每个 w 重新算 10000 行的哈希，代码复杂度上升不少。这道题数据规模实在不大，老老实实逐字符比较是目前最稳、最不会写错的做法。如果你想追求极致性能，可以后面再优化成哈希版，但不建议一开始就这么做。

6. 踩坑实录与常见问题排查

6.1 取 max 循环节的反例

我前面已经提过 max 循环节会出错，这里再详细说一个反例。假设矩阵是：

ababab abcabc

R = 2，C = 6。第一行最小弱周期是 2，第二行最小弱周期是 3。如果按照“每行最小循环节取 max”的做法，W = 3，然后纵向 KMP 得到 H = 2，最终面积 6。但这个方案并不合法，因为第一行以 W = 3 重复出来是 "abaaba"，不是 "ababab"。

正确枚举的结果是什么？W = 6 通过横向检查，H = 1，面积也是 6。所以取 max 的答案碰巧和正确答案一样，但理由站不住脚。如果数据再复杂一点，比如三行、四行的最小周期互相干扰，错误的 max 做法就可能给出小于真实最小面积的错误答案。枚举 W 虽然看起来“笨”，但胜在正确性有保证。

6.2 求横向周期时下标取模错误

横向检查的代码是：

if (mat[i][j] != mat[i][j % w])

有人会把 j % w 写成 j - w，或者只在 j >= w 时才比较。需要注意，j % w 处理的是“当前列对应模式中的第几列”，对于任意 j 都应该成立。比如 w = 3，j = 5 时对应列 2，因为 5 % 3 = 2；j = 2 时对应列 2，两者应该相等。一定要保证所有 j 都用取模后的位置。

6.3 KMP 前缀函数比较的对象不统一

在 getHeight 中，我们比较的是 mat[i][j] 和 mat[pi[i-1]][j]，也就是第 i 行和第 pi[i - 1] 行的前 w 个字符。有人可能会比较 mat[i][j] 和 mat[j][i] 之类的错误写法，导致莫名其妙 WA。想清楚一点：这里的“字符”不是单个字符，而是整行模式；所以 KMP 操作的序列是行序列，不是列序列。

6.4 边界情况：只有一行或只有一列

如果 R = 1，那么 KMP 的 pi 数组长度为 1，getHeight 返回 1。这时答案就是最小的合法 W，也就是这一行字符串的最小覆盖周期。如果 C = 1，那么枚举宽度 W 只有 1 一种，横向检查一定通过，纵向 KMP 求的就是原矩阵每一行构成的序列的循环节。这两种边界情况都应该输出正确的面积。

6.5 读入换行符的问题

如果使用 cin 读入字符串，一般没问题。但如果你用 getline，就要小心缓存区里残留的换行符。建议统一用 cin >> mat[i]，因为题目没有空格，这样做最省事。另外记得关闭 C 风格 IO 同步，否则 10000 行字符串读入可能拖慢速度。

7. 从这道题还能带走什么

7.1 二维问题转一维的通用套路

奶牛矩阵最值得学习的不是 KMP 本身，而是“将二维矩阵按某种方式压缩成一维序列”的思路。当宽度 W 固定后，每一行被压缩成一个定长字符串，矩阵的行序列就变成了一个普通的一维数组。这种压缩思路在很多矩阵题里都能用。

比如判断两个矩阵能否通过循环平移匹配，可以先横向哈希再纵向 KMP；又比如找二维最大重复块，也可以用类似的分步思路。核心就是：先用小维度的暴力枚举锁定一个参数，再把剩下的问题交给成熟的一维算法。

7.2 小维度参数的枚举设计

C 只有 75，所以枚举 W 是可行的；R 很大，所以不能枚举 H。这种“枚举小维、算法处理大维”的思路，比硬套二维 KMP 实用得多。下次遇到规模严重不对称的题目，先想想哪一个维度小到可以暴力，哪一个维度大到必须用数据结构或字符串算法。

7.3 延伸：字符串哈希加速比较

如果 C 也很大，比如到了 1000，那么逐字符比较每一行的前 W 个字符就会变得昂贵。这时可以把每行的前 W 个字符算出一个滚动哈希值，KMP 中比较哈希值而不是字符。但是要注意哈希冲突，双哈希或者用 unsigned long long 自然溢出会稳定很多。奶牛矩阵这道题用不上，但如果你想用更快的姿势交题，这是一个很好的优化方向。

我个人在实际刷题中的体会是：这种带“巧妙暴力”标签的题，真正的坑往往不是算法难写，而是你自以为找到了一个更简单的结论，结果那个结论只对部分数据成立。奶牛矩阵就是一个典型例子。老老实实枚举宽度，再让 KMP 处理高度，最坏情况不过 1 亿次字符比较，换来的是正确性上的绝对安心。先暴力后 KMP，这道题足够让你把二维周期问题彻底想透。