POJ 2185 Milking Grid：KMP + LCM 求最小覆蓋矩陣

問題建模

給定 n×m 字符矩陣，尋找面積最小的「覆蓋矩陣」，使得原矩陣可由該覆蓋矩陣在水平和垂直方向重複鋪貼得到。等價於：分別求每行的最小周期長度（水平周期）和每列的最小周期長度（垂直周期），然後取所有行周期的 LCM 作為覆蓋矩陣寬度，所有列周期的 LCM 作為高度，面積即為兩者乘積。

關鍵技術：KMP 求最小周期

對於長度為 L 的字符串 S，利用 KMP 的 next 數組，其最小周期為 L - next[L]（前提是 L 能被該值整除，否則周期為 L）。本題中，對每行調用 Getnext1 求水平周期，對每列調用 Getnext2 求垂直周期。

算法步驟

1. 輸入矩陣。
2. 對每行計算周期 p_i，累積 width = LCM(width, p_i)。若中途 width > m，直接置為 m 並跳出（因周期不能超過原長度）。
3. 對每列計算周期 q_j，累積 height = LCM(height, q_j)。同理超過 n 則置為 n。
4. 輸出 width * height。

複雜度

• 時間：O(n·m) 計算 next 數組 + O(n + m) 計算 LCM，總體 O(n·m)。
• 空間：O(max(n, m)) 存儲 next 數組。

參考代碼（C++）

int GetNextRow(int r) { // 第 r 行
    int i = 0, j = -1; next[0] = -1;
    while (i < m) {
        if (j == -1 || a[r][i] == a[r][j]) next[++i] = ++j;
        else j = next[j];
    }
    return m - next[m];
}

int GetNextCol(int c) { // 第 c 列
    int i = 0, j = -1; next[0] = -1;
    while (i < n) {
        if (j == -1 || a[i][c] == a[j][c]) next[++i] = ++j;
        else j = next[j];
    }
    return n - next[n];
}

int lcm(int a, int b) {
    int t = a * b;
    while (b) { int r = a % b; a = b; b = r; }
    return t / a;
}

總結

本題將二維周期問題分解為兩個一維周期問題，巧妙應用 KMP 的 next 數組求最小周期，再用 LCM 合併。代碼簡短高效，是字符串周期與矩陣覆蓋結合的優秀範例。