学步园

最小矩形覆盖。。真心好题目。。 

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int const MAXN = 10010;
char str[MAXN][100];
int next[MAXN];
int r,c;
inline int Gcd(int a,int b){
    if(!b) return a;
    return Gcd(b,a%b);
}
inline int Lcm(int a,int b){
    return a * b / Gcd(a,b);
}
inline int Get_R(int x){
    for(int i = 1;i < c;i++){
        int j = next[i];
        while(j && str[x][i] != str[x][j]) j = next[j];
        if(str[x][i] == str[x][j]) next[i + 1] = j + 1;
        else next[i + 1] = 0;
    }
    return c - next[c];
}
inline int Get_C(int x){
    for(int i = 1;i < r;i++){
        int j = next[i];
        while(j && str[j][x] != str[i][x])j = next[j];
        if(str[j][x] == str[i][x]) next[i + 1] = j + 1;
        else next[i + 1] = 0;
    }
    return r - next[r];
}
int main(){
    while(~scanf("%d%d",&r,&c)){
        for(int i = 0;i < r;i++){
            scanf("%s",str[i]);
        }
        int s = 1;
        for(int i = 0;i < r;i++){
            memset(next,0,sizeof(next));
            s = Lcm(s,Get_R(i));
            if(s >= c) s = c;
        }
        int s1 = 1;
        for(int i = 0;i < c;i++){
            memset(next,0,sizeof(next));
            s1 = Lcm(s1,Get_C(i));
            if(s1 >= r) s1 = r;
        }
        printf("%d\n",s1 * s);
    }
    return 0;
}