POJ 2185 Milking Grid：二维 KMP + Next 数组求最小周期子矩阵

题目大意

给定 R×C 字符矩阵（R≤10000, C≤75），求最小面积子矩阵，使其平铺可覆盖原矩阵（子矩阵尺寸不必整除原尺寸）。

核心洞察：行/列独立周期性

1. 将每行视为字符串，求行方向最小周期 → 子矩阵高度
2. 转置矩阵，同理求列方向最小周期 → 子矩阵宽度
3. 面积 = 高度 × 宽度

KMP Next 数组求周期

字符串 s[0..n-1] 的最小周期长度 = n - next[n]，其中 next 为 KMP 失效函数（next[i] = 前缀函数值）。

C++ 实现

#include <cstdio>
#include <cstring>
char s[10005][80], rs[80][10005];
int R[10005], C[10005];
int r, c;

void getNextR() { // 行方向
    R[0] = -1;
    int i = 0, j = -1;
    while (i < r) {
        if (j == -1 || strcmp(s[i], s[j]) == 0) {
            ++i; ++j; R[i] = j;
        } else j = R[j];
    }
}

void getNextC() { // 列方向（转置后）
    C[0] = -1;
    int i = 0, j = -1;
    while (i < c) {
        if (j == -1 || strcmp(rs[i], rs[j]) == 0) {
            ++i; ++j; C[i] = j;
        } else j = C[j];
    }
}

int main() {
    while (scanf("%d%d", &r, &c) != EOF) {
        for (int i = 0; i < r; ++i) scanf("%s", s[i]);
        getNextR();
        for (int i = 0; i < r; ++i)
            for (int j = 0; j < c; ++j)
                rs[j][i] = s[i][j];
        getNextC();
        printf("%d\n", (r - R[r]) * (c - C[c]));
    }
    return 0;
}

样例解析

2 5
ABABA
ABABA

• 行周期：两行相同 → 高度 = 2 - next[2] = 2 - 1 = 1
• 列周期：ABABA → 宽度 = 5 - next[5] = 5 - 3 = 2
• 面积 = 1 × 2 = 2（模式 "AB"）

复杂度

• 时间：O(R·C + R + C) —— 线性扫描
• 空间：O(R·C) 存矩阵

扩展

二维模式匹配（如在大图中找小图）可用 2D KMP/Rabin-Karp，本题利用周期性简化为两次 1D KMP。