/*
* POJ_1961.cpp
*
* Created on: 2013年10月29日
* Author: Administrator
*/
#include <iostream>
#include <cstdio>
#include <cstring>
const int maxn = 1000005;//在IDE测试时可能会报错,因为可能它开不了那么大的数组,这是需要把maxn调小一点来进行测试
int main() {
int n;
int counter = 1;
while (scanf("%d", &n) != EOF, n) {
char str[maxn];
scanf("%s", str);
int len = strlen(str);
int suffix[maxn + 1];
//应用KMP算法计算单词w的前缀函数
suffix[0] = -1;
suffix[1] = 0;
int cur, p = 0;
for (cur = 2; cur <= len; ++cur) {
while (p >= 0 && str[p] != str[cur - 1]) {
p = suffix[p];
}
suffix[cur] = ++p;
}
if(counter != 1){
printf("\n");
}
printf("Test case #%d\n",counter++);
int i;
/**
* POJ_2406 :其实求的是整个串的循环节数,而
* POJ_1961 :求的是一个串到第i个字符时所出现的循环节数...也就是多了一个循环而已
*
*/
for (i = 1; i <= n; ++i) {
//如果len是(len - suffix[len])的前缀,即,假如当前的重复串的长度能被原串的长度整除...
if ((i % (i - suffix[i])) == 0 &&(i / (i - suffix[i])>1)) {
printf("%d %d\n", i ,(i / (i - suffix[i])));
}
}
}
return 0;
}
分享到:
相关推荐
02.北大POJ题库使用指南.docx02.北大POJ题库使用指南.docx02.北大POJ题库使用指南.docx02.北大POJ题库使用指南.docx02.北大POJ题库使用指南.docx02.北大POJ题库使用指南.docx02.北大POJ题库使用指南.docx02.北大POJ...
1 字符串处理 5 1.1 KMP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2 e-KMP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ....
在进行ACM编程训练时做字符串专题的一些题目(POJ1782,POJ1790,POJ1951,POJ2003,POJ2121)
北大POJ1016-Numbers That Count【字符串处理】 解题报告+AC代码
1.文章统计2.特殊要求字符串3.删除字符4.字符串比较5. 字符串排序6.字符串逆序7分离单词8.字符串复制9.字符串替换11.//字符串左右中12.The Clock13.Coin Test 14.Music Composer
LeetCode判断字符串是否循环 :bookmark_tabs:Plan 动态规划 背包问题 动态规划 POJ 3267 POJ 1260 POJ 1015 POJ 3176 POJ 1080 POJ 1159 POJ 2533 POJ 1836 Leetcode 70 Leetcode 309 搜索 DFS POJ 2488 POJ 3083 ...
POJ1048,加强版的约瑟夫问题 难度中等
只是poj上的一条题目,对于理解后缀数组很有帮助.poj3261
poj.grids.cn题型汇总 Dp状态设计与方程总结 1.不完全状态记录 青蛙过河问题 利用区间dp 2.背包类问题 <1> 0-1背包,经典问题 无限背包,经典问题 判定性背包问题 带附属关系的背包问题 <5> + -1背包问题 ...
包含15类的POJ推荐50题,可全面复习或学习算法。 除此外还包含三种级别的水平(初级、中级、高级)应掌握的算法及数据结构及... (poj3096,poj3007)(2)较为复杂的模拟题的训练(poj3393,poj1472,poj3371,poj1027,poj2706)
上面可能有poj的题目,hdu的题目,spoj的题目,sgu的题目,hust上的题目,fzu上的题目
(poj1860,poj3259,poj1062,poj2253,poj1125,poj2240) (3)最小生成树算法(prim,kruskal) (poj1789,poj2485,poj1258,poj3026) (4)拓扑排序 (poj1094) (5)二分图的最大匹配 (匈牙利算法) (poj3041,poj3020) ...
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
我最近做的几个poj题目源代码,可能比较简单
北大POJ1005-I Think I Need a Houseboat 解题报告+AC代码
poj上第1990题目源码,用到了2个树状数组,这题数据结构是关键,想到了题目就很简单了
poj题目2775文件子目录源代码,递归经典题目,
poj nwpu 2013 年才语言答案,不是全部,仅供参考