Period(poj 1961)

时间:2022-01-12 09:35:15

题目大意:

给你一个字符串,求这个字符串到第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)的更多相关文章

  1. JMeter之Ramp-up Period(in seconds)说明(可同时并发)

    Ramp-up Period(in seconds) [1]决定多长时间启动所有线程.如果使用10个线程,ramp-up period是100秒,那么JMeter用100秒使所有10个线程启动并运行. ...

  2. JMeter之Ramp-up Period(in seconds)说明

    Ramp-up Period(in seconds) [1]决定多长时间启动所有线程.如果使用10个线程,ramp-up period是100秒,那么JMeter用100秒使所有10个线程启动并运行. ...

  3. JMeter之Ramp-up Period(in seconds)说明(可同时并发)(转载)

    Ramp-up Period(in seconds) [1]决定多长时间启动所有线程.如果使用10个线程,ramp-up period是100秒,那么JMeter用100秒使所有10个线程启动并运行. ...

  4. LA 3026 &amp&semi;&amp&semi; POJ 1961 Period (KMP算法)

    题意:给定一个长度为n字符串s,求它每个前缀的最短循环节.也就是对于每个i(2<=i<=n),求一个最大整数k>1(如果存在),使得s的前i个字符组成的前缀是某个字符串重复得k次得到 ...

  5. 01背包问题:Charm Bracelet (POJ 3624)(外加一个常数的优化)

    Charm Bracelet    POJ 3624 就是一道典型的01背包问题: #include<iostream> #include<stdio.h> #include& ...

  6. Scout YYF I(POJ 3744)

    Scout YYF I Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 5565   Accepted: 1553 Descr ...

  7. 广大暑假训练1(poj 2488) A Knight&&num;39&semi;s Journey 解题报告

    题目链接:http://vjudge.net/contest/view.action?cid=51369#problem/A   (A - Children of the Candy Corn) ht ...

  8. jmeter之Ramp-up Period(in seconds)

    [1]决定多长时间启动所有线程.如果使用10个线程,ramp-up period是100秒,那么JMeter用100秒使所有10个线程启动并运行.每个线程会在上一个线程启动后10秒(100/10)启动 ...

  9. Games&colon;取石子游戏(POJ 1067)

    取石子游戏 Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 37662   Accepted: 12594 Descripti ...

随机推荐

  1. 上海闪酷成为京东商城第一批独立软件开发商&lpar;ISV&rpar;

    闪酷信息技术(上海)有限公司一直致力于为品牌企业提供电子商务软件及其服务,为其拓展电商渠道保驾护航.上海闪酷依据多年的行业经验和技术积累,与中国 最大的B2C商城达成战略合作,为其2万多家品牌供应商提 ...

  2. java内部类技术提炼

    创作时间:2016.07.28,2016.07.29 本人qq:992591601,欢迎交流. 参考书籍:<Thinking in Java>.<Effective Java> ...

  3. Win7下硬盘安装Centos5&period;3

    前提声明:一个硬盘最多只能有四个主分区,也就是hda1,hda2,hda3和hda4,逻辑分区都是从hda5开始 一.软件准备:EasyBCD+分区助手+Centos 5.3 ISO镜像文件: 二.W ...

  4. HDU5627--Clarke and MST (bfs&plus;位运算)

    http://www.cnblogs.com/wenruo/p/5188495.html Clarke and MST Time Limit: 2000/1000 MS (Java/Others) M ...

  5. 关于时间的操作(JavaScript版)——依据不同区时显示对应的时间

    如今项目基本上告一段落了,难得有一定的闲暇,今天利用数小时完毕了一个功能模块--依据不同区时显示对应的时间,这方面网上基本没有现成的样例,如今将代码粘贴例如以下: <!DOCTYPE HTML ...

  6. C&plus;&plus;著名程序库的比较和学习经验&lpar;STL&period;Boost&period;GUI&period;XML&period;网络等等&rpar;

    1.C++各大有名库的介绍--C++标准库 2.C++各大有名库的介绍--准标准库Boost 3.C++各大有名库的介绍--GUI 4.C++各大有名库的介绍--网络通信 5.C++各大有名库的介绍- ...

  7. Git配合Tag的代码回滚

    现有的远程仓库版本的tag为v1.0 前置准备 具体操作: 我们在本地修改一下readme文件,然后进行add,commit操作. 再给我们的commit打上tag git tag -a v1.1 - ...

  8. for循环找出2到100的质数(素数)

    思路: 1,一个数只有1和它本身两个因数,这个数叫质数. 2.注意:缩进这里else是for循环这个上下文的. 代码: for num in range(2,100): #为大循环变量num提供2-1 ...

  9. lombok自带的sl&fjlig;使用方法

    1.pom.xml <dependency> <groupId>org.projectlombok</groupId> <artifactId>lomb ...

  10. TOP100summit2017:Riot Games 李仁杰——大数据落地要找到数据和经验的平衡点

      壹佰案例:李仁杰老师您好,很荣幸您能参加第六届TOP100全球软件案例研究峰会,您在大数据和人工智能领域有非常丰富的经验,在这次大会上您将分享什么内容? 李仁杰:这次我主要分享的有两个方面. 一个 ...