[HDU 1358]Period[kmp求周期]
2024-10-21 19:42:12
题意:
每一个power前缀的周期数(>1).
思路:
kmp的next. 每一个前缀都询问一遍.
#include <cstring>
#include <cstdio>
const int MAXN = 1000005;
int next[MAXN];
char s[MAXN];
//93MS 5092K
void prekmp()
{
next[0] = -1;
int j = -1;
for(int i=1;s[i];i++)
{
while(j!=-1 && s[j+1]!=s[i]) j = next[j];
if(s[j+1]==s[i]) j++;
next[i] = j;
}
} int main()
{
int n,cas = 0;
while(scanf("%d",&n) && n)
{
scanf("%s",s);
printf("Test case #%d\n",++cas);
prekmp();
int len;
for(int i=1;i<n;i++)
{
len = i-next[i];
int k;
if(!((i+1)%len))
{
if((k=(i+1)/len)>1)
printf("%d %d\n",i+1,k);
}
}
printf("\n");
} }
最新文章
- iOS开发系列--Swift 3.0
- 实验三 敏捷开发与XP实践
- 只写104行代码!在nopCommerce中如何实现自动生成网站地图
- IOS&;swift开发常用的网站
- 停止使用循环 教你用underscore优雅的写代码
- Hadoop命令摘录
- Ubuntu 12.04 中安装和配置 Java JDK
- informix 查看数据库空间名
- 如何让Activiti-Explorer使用sql server数据库
- CoreAnimation3-专用图层
- C语言 结构体数组保存到二进制文件中
- cv::Mat类之type成员
- K3 WISE 开发插件《K3 WISE常用数据表整理》
- arcengine Annotation研究的一些学习资料(转)FeatureWeight
- iOS中app的分发测试
- Winform控件学习笔记【第四天】——WebBrowser
- Google Drive 里的文件下载的方法
- asp.net MVC 多系统目录结构
- ngx_lua实现登录逻辑
- BZOJ2209: [Jsoi2011]括号序列
热门文章
- Oracle游标-循环查询表中数据(表名),并执行
- 五毛的cocos2d-x学习笔记01-创建项目
- JavaBean的一个小例子
- C++对C语言的非面向对象特性扩充(1)
- 手把手教你图片转ASCII码图
- Poj 2092 Grandpa is Famous(基数排序)
- Wiki: HSL和HSV色彩空间
- MCU开发之I2C通信
- BestCoder Round #50 (div.1) 1002 Run (HDU OJ 5365) 暴力枚举+正多边形判定
- Google Code Jam Round 1A 2015 Problem B. Haircut 二分