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:这个稍微改一下就对了~

Posted by 271855 at 2011-05-11 19:32:46 on Problem 2185
In Reply To:这个稍微改一下就对了~ Posted by:Iamjw at 2010-12-18 03:27:35
> 比如:
> 2 8
> aaabcaaa
> abababab
> 这个思路会给出16吧?但是答案是12。因为横排的计算出错了~
> 
> 其实是因为第一个串符合题意的长度不止5,还有6,7,8。
> 所以事实上应该把每个串符合题意的长度都记录下来,然后选一个公共最小的。
> 
> 比如第一个串是 5,6,7,8
> 第二个串是2,4,6,8
> 所以横排应该选6。
> 
> 这里只需解决两个问题:
> 1) 如何找到串s的所有符合题意的长度?
>     只需要对s进行一次kmp特征值计算,如果发现后面有多余的后缀,就把后缀再拿来做一次kmp,不断重复,直到没有后缀。这个过程就可以记录所有符合题意的串了。
>     比如aaabcaaa,先求一遍kmp,得到5,再对后缀aaa求一遍,得到1(即6,7,8)。
>     又比如aabaabaabaa,先求一遍kmp,得到3(即3,6,9),再对后缀aa求一遍,得到1,(即10,11)。
> 
> 2) 如何找到所有串公共的最短符合题意的长度?
>     直接用(列数)c个桶来统计一下就行了~ 如果某个长度出现了(行数)r次,那么它就是公共的。最后从小到大遍历一遍就求出了最小长度。
> 
神人,这都能想出来。。
膜拜啊~

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