记录编号	583209	评测结果	AAAAAAAAAAWAA
题目名称	3593.[POJ 2185]Milking Grid	最终得分	92
用户昵称	┭┮﹏┭┮	是否通过	未通过
代码语言	C++	运行时间	0.008 s
提交时间	2023-10-07 19:09:00	内存使用	1.57 MiB

#include <bits/stdc++.h> 
using namespace std;
const int N = 1e4+10;
int n,m;
char a[N][110];
int ne[110],nx[N],ans1 = 1,ans2 = 1;
int gcd(int x,int y){
    if(y == 0)return x;
    if(x % y == 0)return y;
    return gcd(y,x%y);
}
int main(){
    freopen("mgrid.in","r",stdin);
    freopen("mgrid.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int l = 1;l <= n;l++){
        scanf("%s",a[l]+1);
        int i = 2,j = 0;
        memset(ne,0,sizeof(ne));
        for(;i <= m;i++){
            while(j > 0 && a[l][i] != a[l][j+1])j = ne[j];
            if(a[l][i] == a[l][j+1])j++;
            ne[i] = j;
        }
        int s = m - ne[m];
        ans1 = ans1 * s / gcd(ans1,s);
    }
    ans1 = min(ans1,m);
    for(int l = 1;l <= ans1;l++){
        int i = 2,j = 0;
        memset(nx,0,sizeof(nx));
        for(;i <= n;i++){
            while(j > 0 && a[i][l] != a[j+1][l])j = nx[j];
            if(a[i][l] == a[j+1][l])j++;
            nx[i] = j;
        }
        int s = n - nx[n];
        ans2 = ans2 * s / gcd(ans2,s);
    }
    ans2 = min(ans2,n);
    printf("%d\n",ans1*ans2);

    
    return 0;
    
}