题意分析

本题要求在农夫约翰的奶牛挤奶形成的R行C列的矩形网格中，找到面积最小的矩形单元，通过重复平铺该单元能够构成整个挤奶网格。网格中的每个位置用一个大写字母表示奶牛的品种。需要注意的是，最小矩形单元的长和宽不需要能整除整个网格的长和宽。例如给定输入2行5列的网格 ABABA ABABA，最小的矩形单元是 AB，虽然 2 不能整除 5，但通过重复平铺 AB 可以得到整个网格。最终需要输出这个最小矩形单元的面积。

解题思路

确定行方向最小重复单元长度：

对于每一行，从长度1开始枚举可能的重复单元长度len。

检查该行从起始位置开始长度len的子串，是否能通过重复拼接形成该行完整字符串。例如对于字符串 ABABA，当len = 1时，子串 A 重复无法得到原字符串；当len = 2时，子串 AB 重复拼接 ABABAB 截取前5个字符可得到原字符串，所以该行最小重复单元长度为2。

记录每一行的最小重复单元长度，取所有行最小重复单元长度的最大公约数x，作为整个网格在行方向的最小重复单元长度。因为只有长度为最大公约数的单元，才能保证在所有行都能以相同的方式重复构成。

确定列方向最小重复单元行数：

将整个网格按列进行分析，从行数1开始枚举可能的重复单元行数num。

检查从起始行开始，高度为num的列子矩阵，是否能通过重复拼接形成整个列。例如有两行 ABABA ABABA，当num = 1时，第一行的列子矩阵重复无法得到两行列；当num = 2时，两行组成的列子矩阵重复可得到整个列，所以列方向最小重复单元行数为2。

记录最小重复单元行数y。

计算最小矩形单元面积：

最小矩形单元的面积即为行方向最小重复单元长度x与列方向最小重复单元行数y的乘积，即$x \times y$ ，将其输出即为最终答案。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
const int maxh=10010;
const int maxw=82;
char g1[maxh][maxw];
char g2[maxw][maxh];
int nextval[10010]; // 使用之前建议的重命名方案
int n,m;

void readdata(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++) scanf("%s",g1[i]);
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++) 
            g2[j][i]=g1[i][j];
}

int nexts(char p[],int len){
    nextval[0]=-1;
    int k=-1,sum=1;
    for(int i=1;i<len;i++){
        while(k>=0 && p[k+1]!=p[i]) k=nextval[k];
        if(p[k+1]==p[i]) k=k+1;
        nextval[i]=k;
        if(k==-1) sum=i+1;
        else if(i+1-k>sum) sum=i-k;    
    }    
    return sum;
}

int gcd(int a,int b){
     int r;
     while(b){
          r=a%b;
          a=b;
          b=r;         
     }   
     return a;
}

int lcm(int a,int b){ return a*b/gcd(a,b); }

int solve(){
    int cnt1=1,cnt2=1;
    for(int i=0;i<n;i++){
        cnt1=lcm(cnt1,nexts(g1[i],m));
        if(cnt1>=m){ cnt1=m; break; }
    }
    for(int i=0;i<m;i++){
        cnt2=lcm(cnt2,nexts(g2[i],n));
        if(cnt2>=n){ cnt2=n; break; }
    }
    return cnt1*cnt2;
}

int main(){
    readdata();
    printf("%d\n",solve());
    system("pause");
    return 0;
}
```

```