这道题是昨天晚上9点多看的,今天早上来了后想了想,,感觉有思路了,吃过饭后就ac了,,,没注意到数据大小,,吃了一次re。。。。。。。这道题算是next数组的一个应用,,,有点折半查找的感觉,,,求字符串循环节和这道题,都是next数组的妙用,,,看来对next数组有一个清晰的理解非常必要啊!题目:
Seek the Name, Seek the Fame
Time Limit:2000MS |
|
Memory Limit:65536K |
Total Submissions:6869 |
|
Accepted:3207 |
Description
The little cat is so famous, that many couples tramp over hill and dale to Byteland, and asked the little cat to give names to their newly-born babies. They seek the name, and at the same time seek the fame. In order to escape from such boring job, the innovative
little cat works out an easy but fantastic algorithm:
Step1. Connect the father's name and the mother's name, to a new string S.
Step2. Find a proper prefix-suffix string of S (which is not only the prefix, but also the suffix of S).
Example: Father='ala', Mother='la', we have S = 'ala'+'la' = 'alala'. Potential prefix-suffix strings of S are {'a', 'ala', 'alala'}. Given the string S, could you help the little cat to write a program to calculate the length of possible prefix-suffix strings
of S? (He might thank you by giving your baby a name:)
Input
The input contains a number of test cases. Each test case occupies a single line that contains the string S described above.
Restrictions: Only lowercase letters may appear in the input. 1 <= Length of S <= 400000.
Output
For each test case, output a single line with integer numbers in increasing order, denoting the possible length of the new baby's name.
Sample Input
ababcababababcabab
aaaaa
Sample Output
2 4 9 18
1 2 3 4 5
ac代码:
分享到:
相关推荐
POJ各题算法分类和题目推荐 ACM必看 POJ各题算法分类和题目推荐 ACM必看 POJ各题算法分类和题目推荐 ACM必看
NULL 博文链接:https://128kj.iteye.com/blog/1744222
poj1087贪心算法实验报告 poj1087贪心算法实验报告
NULL 博文链接:https://128kj.iteye.com/blog/1757060
POJ中级图算法所有题目【解题报告+AC代码】 我的所有POJ解题报告 http://blog.csdn.net/lyy289065406/article/details/6642573
poj acm题解,包括绝大部分poj题目的题解,可以供acm爱好者学习研究
这是一道很不错的题目,即可以用线段树做也可以用树状数组,可谓经典。不过当然了线段树是比较难搞,而树状数组是极其简洁的,构造很简单,下面就分别来介绍一下两种方法...
POJ各题算法分类和题目推荐.pdf
poj上的算法题目分类,对于大家想练习算法的同鞋可以参考一下,里面按类列出了各种算法的题号。
前缀周期代码,解决POJ上的问题,KMP的NEXT数组应用
供初学编程基本算法的人练习使用,在poj.grids.cn上
解决算法问题 poj1082, poj1150, poj1180, poj1201, poj1222,代码完成所给题目要求。
北大POJ初级-图算法 解题报告+AC代码
北大POJ初级-基本算法 解题报告+AC代码
POJ题目分类,列出了所有的类目,里面写了一些很好的框架。
POJ上的一道题目,自己写的代码,因为想下载别人的, 所以就放上了。
poj 上的几道kmp 题的解题报告 sourse code of kmp algorithm
NULL 博文链接:https://128kj.iteye.com/blog/1747400
关于C++ 算法 北大网站POJ 八数码问题
北大POJ中级-基本算法 解题报告+AC代码