题目大意

给定一个 $n \times m$ 的字符网格，需要找到所有可能的模板长度 $k$，使得：

• 存在一个长度为 $k$ 的横向模板，可以完整印刷所有行
• 存在一个长度为 $k$ 的纵向模板，可以完整印刷所有列
• 横向和纵向模板的内容完全相同

算法思路

核心观察

1. 周期性原理：如果模板长度为 $k$，那么每行的内容必须是以某个长度为 $k$ 的字符串为循环节
2. 行列约束：模板长度必须同时满足所有行的周期约束和所有列的周期约束
3. 内容一致：横向模板和纵向模板实际上是同一个字符串，只是应用方向不同

关键步骤

步骤1：分析每行的最小周期

对于每一行字符串 $s$，使用 KMP算法 计算其最小周期长度：

• 计算 KMP 的 next 数组
• 最小周期长度 = len - next[len-1]
• 如果 len % period != 0，则周期长度为 len

步骤2：分析每列的最小周期

• 将网格转置，对每列同样进行周期性分析
• 得到所有列的最小周期长度

步骤3：寻找可行的模板长度

对于候选长度 $k$，必须满足：

1. $k$ 能整除所有行的最小周期长度
2. $k$ 能整除所有列的最小周期长度
3. 横向模板内容 = 纵向模板内容

步骤4：验证模板内容一致性

对于每个候选长度 $k$：

• 横向模板：取第一行的前 $k$ 个字符
• 纵向模板：取第一列的前 $k$ 个字符
• 检查这两个字符串是否相同

复杂度分析

• 时间复杂度：$O(n \times m)$
  • KMP 算法处理每行：$O(m)$
  • KMP 算法处理每列：$O(n)$
  • 总共：$O(n \times m + m \times n) = O(n \times m)$
• 空间复杂度：$O(n \times m)$

代码实现

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
using namespace std;

// 使用KMP算法计算字符串的最小周期长度
int computePeriod(const string& s) {
    int n = s.length();
    vector<int> next(n, 0);
    
    // 构建KMP的next数组
    for (int i = 1; i < n; i++) {
        int j = next[i-1];
        while (j > 0 && s[i] != s[j]) {
            j = next[j-1];
        }
        if (s[i] == s[j]) {
            j++;
        }
        next[i] = j;
    }
    
    int period = n - next[n-1];
    if (n % period == 0) {
        return period;
    }
    return n;
}

// 获取所有的因数
vector<int> getDivisors(int x) {
    vector<int> divisors;
    for (int i = 1; i * i <= x; i++) {
        if (x % i == 0) {
            divisors.push_back(i);
            if (i != x / i) {
                divisors.push_back(x / i);
            }
        }
    }
    sort(divisors.begin(), divisors.end());
    return divisors;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m;
    
    vector<string> grid(n);
    for (int i = 0; i < n; i++) {
        cin >> grid[i];
    }
    
    // 步骤1：计算每行的最小周期
    vector<int> rowPeriods(n);
    for (int i = 0; i < n; i++) {
        rowPeriods[i] = computePeriod(grid[i]);
    }
    
    // 步骤2：计算每列的最小周期
    vector<string> transposed(m, string(n, ' '));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            transposed[j][i] = grid[i][j];
        }
    }
    
    vector<int> colPeriods(m);
    for (int j = 0; j < m; j++) {
        colPeriods[j] = computePeriod(transposed[j]);
    }
    
    // 步骤3：找到所有行的周期长度的公约数
    set<int> candidateLengths;
    vector<int> rowDivisors = getDivisors(rowPeriods[0]);
    
    for (int div : rowDivisors) {
        bool valid = true;
        for (int i = 1; i < n; i++) {
            if (rowPeriods[i] % div != 0) {
                valid = false;
                break;
            }
        }
        if (valid) {
            candidateLengths.insert(div);
        }
    }
    
    // 步骤4：找到所有列的周期长度的公约数  
    set<int> colCandidateLengths;
    vector<int> colDivisors = getDivisors(colPeriods[0]);
    
    for (int div : colDivisors) {
        bool valid = true;
        for (int j = 1; j < m; j++) {
            if (colPeriods[j] % div != 0) {
                valid = false;
                break;
            }
        }
        if (valid) {
            colCandidateLengths.insert(div);
        }
    }
    
    // 步骤5：求交集并验证内容一致性
    vector<int> result;
    for (int k : candidateLengths) {
        if (colCandidateLengths.count(k)) {
            // 检查横向模板和纵向模板内容是否相同
            string horizontal = grid[0].substr(0, k);
            string vertical;
            for (int i = 0; i < k; i++) {
                vertical += grid[i][0];
            }
            
            if (horizontal == vertical) {
                result.push_back(k);
            }
        }
    }
    
    // 输出结果
    cout << result.size() << "\n";
    for (int i = 0; i < result.size(); i++) {
        if (i > 0) cout << " ";
        cout << result[i];
    }
    cout << "\n";
    
    return 0;
}

样例解析

样例1

输入：
5 8
aabaaaaa
babaabbb
aabaaaaa
aabaaaaa
abaaabaa

输出：
1
4

解释：

• 所有行的最小周期都是4的倍数
• 所有列的最小周期也都是4的倍数
• 长度为4的模板满足所有条件

总结

本题的关键在于将二维的模板匹配问题转化为：

1. 对行和列分别进行周期性分析
2. 使用数论方法找到公约数
3. 验证内容一致性

通过KMP算法高效计算最小周期，再结合因数分解和集合运算，可以在 $O(n \times m)$ 时间内解决问题。