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

so

Posted by tayu at 2005-10-10 14:53:48 on Problem 2185
给出一个字母组成的矩阵,找出一个最小的子矩阵,使得这个子矩阵的无限复制扩张之后的矩阵包含原来的矩阵,例如
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