问题描述
每天早晨约翰的奶牛都会在挤奶的时候排成阵列，即站成R(1<=R<=10000)行C(1<=C<=75)列的矩阵。我们知道，约翰是奶牛专家，他打算写一本关于喂养奶牛的书，他发现，当奶牛按不同血统标记以后，整个大矩阵就像由很多小矩阵无缝拼接的一样。 请帮助约翰找到面积最小的模型矩阵，使他能拼出整个大矩阵，当然，模型矩阵的尺寸不一定能整除大矩阵，也就是说你可以用若干个模型矩阵，拼出一个包含大矩阵的更大的矩阵。输入格式
第一行， 两个整数R和C 接下来是由大写字母构成的R*C的矩阵输出格式
一个整数，表示最小模型矩阵的面积。样例输入
2 5 ABABA BABAB样例输出
4提示
样例说明： 模型矩阵如下： AB BA 拼出的大矩阵如下： ABABAB BABABA本题usaco官方数据很弱，很多错解可以AC，下面提供两种正确思路。
思路一：
首先明确小矩阵不能够重叠，所以我们考虑循环节。 一个简单的想法是求出每一行和每一列的分别的最小循环节，然后求最小公倍数，把行和列的最小公倍数乘起来，然而这并不是最优解，因为循环节可能有多个，比如 AAABCAAA ABABABAB 这样的数据，两行的最小循环节的最小公倍数是10，算出答案20，然而显然正解是12。 所以我们需要求出每一行所有的循环节，然后求出他们取不同循环节时最小的最小公倍数。 观察可以发现只需要取所有行的最小公共循环节长度即可（因为循环节的倍数也是循环节）。列的处理同理。
思路二：
将每一行Hash成一个数字，然后求形成数列的最小循环节，列同理，然后将两个最小循环节长度乘起来就是答案。这样相当求出了最小循环矩形。
思路二代码（By rgnoH）：
#include<stdio.h> #define ll long long #define mod 0xffff int R,C,fail[10005],rans,cans; ll Hash[10005]; char ch[10005][80]; int main() { int i,j,sd=131; ll h; scanf("%d%d",&R,&C); for(i=1;i<=R;i++)scanf("%s",&ch[i][1]); for(i=1;i<=R;i++) { h=0; for(j=1;j<=C;j++)h=(h+ch[i][j])*sd%mod; Hash[i]=h; } fail[1]=j=0; for(i=2;i<=R;i++) { while(j>0&&Hash[j+1]!=Hash[i])j=fail[j]; if(Hash[j+1]==Hash[i])j++; fail[i]=j; } rans=R-fail[R]; for(i=1;i<=C;i++) { h=0; for(j=1;j<=R;j++)h=(h+ch[j][i])*sd%mod; Hash[i]=h; } fail[1]=j=0; for(i=2;i<=C;i++) { while(j>0&&Hash[j+1]!=Hash[i])j=fail[j]; if(Hash[j+1]==Hash[i])j++; fail[i]=j; } cans=C-fail[C]; printf("%d",cans*rans); }