Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:so

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

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator