[POJ]2185 Milking Grid

Every morning when they are milked, the Farmer John's cows form a rectangular grid that is R (1 <= R <= 10,000) rows by C (1 <= C <= 75) columns. As we all know, Farmer John is quite the expert on cow behavior, and is currently writing a book about feeding behavior in cows. He notices that if each cow is labeled with an uppercase letter indicating its breed, the two-dimensional pattern formed by his cows during milking sometimes seems to be made from smaller repeating rectangular patterns. 

Help FJ find the rectangular unit of smallest area that can be repetitively tiled to make up the entire milking grid. Note that the dimensions of the small rectangular unit do not necessarily need to divide evenly the dimensions of the entire milking grid, as indicated in the sample input below. 

这道题是要我们在输入矩阵M中寻找最小的矩阵m，其在x和y方向上重复之后可以使得新得到的矩阵等于或者包含输入矩阵M。这其实就是二维的最小覆盖子串问题，如果我们把每一行的string看做一维串里的一个char，我们就可以run kmp找到行维度上的最小覆盖长度。列上的每一串string不太好直接比较，但是如果我们对矩阵转置，我们就可以把其转化为行，然后跑kmp找到列上的最小覆盖长度。两者共同就表示了最小覆盖矩阵的大小。时间复杂度O(n * m)，m为行数，n为列数。代码如下：