poj2752Seek the Name, Seek the Fame
2024-10-13 04:49:42
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:)
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.
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
Source
POJ Monthly--2006.01.22,Zeyuan Zhu
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<set>
using namespace std; char s[];
int next[],l;
void f(int t)
{
if(t == ) return;
f(next[t]);
if(t!=l)printf("%d ",t);
else printf("%d\n",t);
} int main()
{
int i,j,k;
while(scanf("%s",s+)!=EOF)
{
l = strlen(s+);
next[] = ;
for(i = ;i<l+;i++)
{
int t = next[i-];
while(t&&s[i]!=s[t+]) t = next[t];
if(s[i] == s[t+]) t++;
next[i] = t;
}
f(l);
}
return ;
}
最新文章
- H5坦克大战之【玩家控制坦克移动2】
- stl文件格式解析代码--java版
- Android Studio自动删除多余的import
- ubuntu16.04下配置JDK 1.8+安装Java EE,并实现最大子数组算法
- ERROR 1045 (28000): Access denied for user &#39;root&#39;@&#39;localhost&#39; (using password: NO)
- 水平ListView类
- Scorpio-CSharp总链接
- Cytoscape.js – 用于数据分析和可视化的交互图形库
- google快捷键,通过浏览器本身来查看
- [转]Entity Framework4.0 (七) EF4的存储过程
- 【WCF--初入江湖】10 序列化和传输大型数据流
- Java泛型 通配符? extends与super
- CString 操作指南
- JavaScript的";类";
- 类别sort使用排序
- XML和JSON两种数据交换格式的比较
- linux下利用shell脚本实现添加crontab任务
- Java中的变量数据类型补充
- 读《图解HTTP》有感-(确保WEB安全的HTTPS)
- css自定义滚动条
热门文章
- .net 链接oracle
- slf4j 和 log4j使用案例
- AdapterView及其子类之一:基本原理(ListView、ListActivity类型)
- plsql基本语法(
- 整理:GET与POST的区别
- gnome-ssh-askpass:No such file or directory &;&; unable to read askpass response
- Linux系统下用C语言获取MAC地址
- mysql拒绝访问(Error 1044/1045)问题的解决
- 最少步数(bfs)
- 数据库sqlite的使用