题目大意:
给你一个字符串,求这个字符串到第i个字符为止的循环节的次数。
比如aabaabaabaab,长度为12.到第二个a时,a出现2次,输出2.到第二个b时,aab出现了2次,输出2.到第三个b时,aab出现3次,输出3.到第四个b时,aab出现4次,输出4.
KMP!!!
#include<cstdio>
#include<iostream>
#include<cstring>
#define M 1000010
using namespace std;
int fail[M],a[M],m;
char ch[M];
void kmp_init()
{
fail[]=;
for(int i=;i<=m;i++)
{
int p=fail[i-];
while(p&&a[p+]!=a[i])p=fail[p];
if(a[p+]==a[i])fail[i]=p+;
else fail[i]=;
}
}
int main()
{
int cnt=;
while()
{
memset(fail,,sizeof(fail));
scanf("%d",&m);
if(m==)break;
cin>>ch;
printf("Test case #%d\n",++cnt);
for(int i=;i<=m;i++)
a[i]=ch[i-];
kmp_init();
for(int i=;i<=m;i++)
{
int x=i-fail[i];
if(i%x==&&x!=i)
printf("%d %d\n",i,i/x);
}
printf("\n");
}
return ;
}
Period(poj 1961)的更多相关文章
-
JMeter之Ramp-up Period(in seconds)说明(可同时并发)
Ramp-up Period(in seconds) [1]决定多长时间启动所有线程.如果使用10个线程,ramp-up period是100秒,那么JMeter用100秒使所有10个线程启动并运行. ...
-
JMeter之Ramp-up Period(in seconds)说明
Ramp-up Period(in seconds) [1]决定多长时间启动所有线程.如果使用10个线程,ramp-up period是100秒,那么JMeter用100秒使所有10个线程启动并运行. ...
-
JMeter之Ramp-up Period(in seconds)说明(可同时并发)(转载)
Ramp-up Period(in seconds) [1]决定多长时间启动所有线程.如果使用10个线程,ramp-up period是100秒,那么JMeter用100秒使所有10个线程启动并运行. ...
-
LA 3026 &;&; POJ 1961 Period (KMP算法)
题意:给定一个长度为n字符串s,求它每个前缀的最短循环节.也就是对于每个i(2<=i<=n),求一个最大整数k>1(如果存在),使得s的前i个字符组成的前缀是某个字符串重复得k次得到 ...
-
01背包问题:Charm Bracelet (POJ 3624)(外加一个常数的优化)
Charm Bracelet POJ 3624 就是一道典型的01背包问题: #include<iostream> #include<stdio.h> #include& ...
-
Scout YYF I(POJ 3744)
Scout YYF I Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 5565 Accepted: 1553 Descr ...
-
广大暑假训练1(poj 2488) A Knight&#39;s Journey 解题报告
题目链接:http://vjudge.net/contest/view.action?cid=51369#problem/A (A - Children of the Candy Corn) ht ...
-
jmeter之Ramp-up Period(in seconds)
[1]决定多长时间启动所有线程.如果使用10个线程,ramp-up period是100秒,那么JMeter用100秒使所有10个线程启动并运行.每个线程会在上一个线程启动后10秒(100/10)启动 ...
-
Games:取石子游戏(POJ 1067)
取石子游戏 Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 37662 Accepted: 12594 Descripti ...
随机推荐
-
上海闪酷成为京东商城第一批独立软件开发商(ISV)
闪酷信息技术(上海)有限公司一直致力于为品牌企业提供电子商务软件及其服务,为其拓展电商渠道保驾护航.上海闪酷依据多年的行业经验和技术积累,与中国 最大的B2C商城达成战略合作,为其2万多家品牌供应商提 ...
-
java内部类技术提炼
创作时间:2016.07.28,2016.07.29 本人qq:992591601,欢迎交流. 参考书籍:<Thinking in Java>.<Effective Java> ...
-
Win7下硬盘安装Centos5.3
前提声明:一个硬盘最多只能有四个主分区,也就是hda1,hda2,hda3和hda4,逻辑分区都是从hda5开始 一.软件准备:EasyBCD+分区助手+Centos 5.3 ISO镜像文件: 二.W ...
-
HDU5627--Clarke and MST (bfs+位运算)
http://www.cnblogs.com/wenruo/p/5188495.html Clarke and MST Time Limit: 2000/1000 MS (Java/Others) M ...
-
关于时间的操作(JavaScript版)——依据不同区时显示对应的时间
如今项目基本上告一段落了,难得有一定的闲暇,今天利用数小时完毕了一个功能模块--依据不同区时显示对应的时间,这方面网上基本没有现成的样例,如今将代码粘贴例如以下: <!DOCTYPE HTML ...
-
C++著名程序库的比较和学习经验(STL.Boost.GUI.XML.网络等等)
1.C++各大有名库的介绍--C++标准库 2.C++各大有名库的介绍--准标准库Boost 3.C++各大有名库的介绍--GUI 4.C++各大有名库的介绍--网络通信 5.C++各大有名库的介绍- ...
-
Git配合Tag的代码回滚
现有的远程仓库版本的tag为v1.0 前置准备 具体操作: 我们在本地修改一下readme文件,然后进行add,commit操作. 再给我们的commit打上tag git tag -a v1.1 - ...
-
for循环找出2到100的质数(素数)
思路: 1,一个数只有1和它本身两个因数,这个数叫质数. 2.注意:缩进这里else是for循环这个上下文的. 代码: for num in range(2,100): #为大循环变量num提供2-1 ...
-
lombok自带的slfj使用方法
1.pom.xml <dependency> <groupId>org.projectlombok</groupId> <artifactId>lomb ...
-
TOP100summit2017:Riot Games 李仁杰——大数据落地要找到数据和经验的平衡点
壹佰案例:李仁杰老师您好,很荣幸您能参加第六届TOP100全球软件案例研究峰会,您在大数据和人工智能领域有非常丰富的经验,在这次大会上您将分享什么内容? 李仁杰:这次我主要分享的有两个方面. 一个 ...