Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:这个稍微改一下就对了~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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator