【题目来源】：https://vjudge.net/problem/HDU-1358 【题意】 给出一个长度为n的字符串，问，在字符1~n个里，前缀是周期串的是哪个？输出i，并且输出这i个字符里最小周期的个数k，并且，k不能是1。 举个例子说明一下： abcabcabcabc 那么输出： 6 2 9 3 12 4。 先是字符串：abcabc，是周期串，最小周期是3，k是2（也就是有两个最小周期），以此类推，。 【思路】 依旧利用kmp中的next数组，这一题类似于Cyclic Nacklace，只不过那一道是给你固定的长度，而这个是给了一个范围，直接for循环暴力。 最重要的是要明白next数组存的内容代表什么，最好自己模拟一遍写出next数组。会发现，当前的长度减去当前的next值就是当前前缀的最下周期。 【代码】
#include<set> #include<map> #include<stack> #include<cmath> #include<queue> #include<cstdio> #include<string> #include<cstring> #include<iostream> #include<limits.h> #include<algorithm> #define mem(a,b) memset(a,b,sizeof(a)) using namespace std; const int mod=1e9+7; const double esp=1e-5; typedef unsigned long long ll; typedef long long LL; char s[1000000+10]; int nexts[1000000+10]; int len; void get_next() { int i=0,j; j=nexts[0]=-1; while(i<len) { while(-1!=j&&s[i]!=s[j]) j=nexts[j]; nexts[++i]=++j; } } int main() { int cases=1; while(~scanf("%d%*c",&len)&&len) { scanf("%s",s); get_next(); // for(int i=0;i<=len;i++) // { // printf("%d ",nexts[i]); // } // printf("\n"); printf("Test case #%d\n",cases++); for(int i=0;i<len;i++) { int x=i+1; int y=x-nexts[x]; if(x%y==0&&x/y!=1) { printf("%d %d\n",x,x/y); } } printf("\n"); } }