> 给出一个字母组成的矩阵，找出一个最小的子矩阵，使得这个子矩阵的无限复制扩张之后的矩阵包含原来的矩阵，例如
> ABABA
> ABABA
> 他的最小重复子矩阵是AB
> 而
> ABAB
> CDCD
> BABA
> DCDC
> 的最小重复子矩阵是
> AB
> CD
> BA
> DC
> 原矩阵的长≤10000，宽≤75
> 本题可能可以利用宽比较小而设计出高效的算法。但是下面的算法不涉及这个问题。
> 算法思想：首先可以证明，最小重复矩阵一定靠左上角。这个证明就略了。那么，我们考虑求出每一行的最小重复串长度，所有行的最小重复串的长度的lcm就是最小重复子矩阵的宽。然后我们对列也做相同的操作。于是我们就可以求得最小重复子矩阵的大小了。（当所得的宽大于原来的宽时，就让他等于原来的宽，当长大于。。。）
> 算法实现：算法的核心在于高效的求出每一行和每一列的最小重复串，这个可以最原串做一次kmp，那么，最后总长度－最后以为的kmp函数值，就是最小重复串的长度。
>应该是假设它不靠左上角也可以转移到左上角

• Re:so (82) guogaoan 2010-04-08 22:34:26