题意是求前n个数的循环节的个数:
例如:aabaabaabaab中 ,
前2个字符aa,循环节为a, 所以为2 2;
前6 个 字符循环节为aab, 所以为6 2;
前9个 字符循环节为aab, 所以为9 3;
前12 个 字符循环节为aab,所以为12 4;
关键是如何求循环节,首先还要熟悉next数组的意思,next[j]=k,表示j前面k个元素与开头的前k个元素相同,但是中间可能有循环的元素,如何去除重复的元素
i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
a[i] | a | a | b | a | a | b | a | a | b | a | a | b | |
next[i] | -1 | 0 | 1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
2*next[i]-i即可以求出中间重复的元素;
(原因:初中因该学过,给N个元素,前k个元素和后k个元素相等,求重复的元素个数)
next[i]-(2*next[i]-i) == i-next[i]即是最小的循环节;
i/最小循环节 = 循环的次数 ;
#include<cstdio> #include<cstring> using namespace std; const int MAX = 1000000 + 5; int next[MAX],len; char a[MAX]; void get_next() { int i=0,j=-1; next[0]=-1; while(i<len) { while(j>-1&&a[j]!=a[i]) j=next[j]; j++; i++; next[i]=j; } } int main() { int ncase=0; while(scanf("%d",&len)&&len) { scanf("%s",a); int circle; get_next(); printf("Test case #%d\n",++ncase); for(int i=1;i<=len;i++) { circle=next[i]-(2*next[i]-i); if(2*next[i]-i>=0 && i%circle == 0) { printf("%d %d\n",i,i/circle); } } printf("\n"); } return 0; }
相关推荐
hdu动态规划算法集锦
hdu ACM代码 每种算法都有分类 大三了,没有时间弄ACM,这些要删了
很实用的算法讲解,hdu的lcy老师讲解,还不错!!
next[i]的含义是在str[i]之前的字符串str[0...i]中,必须以str[i-1]结尾的后缀子串(不能包含str[0])与必须以str[0]开头的前
HDU的ACM,非常的好 涉及了很多算法,例如二分匹配、博弈、组合、最小生成树、搜索、动态规划、贪心算法
杭州电子科技大学oj平台上的第1010题,是关于搜索的题目,很不错的题
HDU-1711 Number Sequence(KMP算法)For each test case, you should output one line wh
acm 技术大牛 课件 HDU 自学必备课件 全套齐全 (lecture_01)初识ACM (lecture_02)简单数学题 (lecture_03)递推求解 (lecture_04)动态规划(1)_ (lecture_05)计算几何基础_ (lecture_06)母函数 (lecture_...
杭电ACM 培训课件,包括各种常用的算法,并结合例题详细的讲解,对提高算法思想用很大帮助
八数码的A*算法~不是很高效,但是很适合刚刚学这个算法的朋友们
算法-数塔(HDU-2084).rar
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
算法-超级楼梯(HDU-2040)(包含源程序).rar
hdu1001解题报告
hdu 1574 passed sorce
算法-六度分离(HDU-1869)(包含源程序).rar
HDU的一题........HDU DP动态规
算法-欧拉回路(HDU-1878)(包含源程序).rar