题目地址:
http://acm.hdu.edu.cn/showproblem.php?pid=1358
题目概述:
给出一个字符串s,求s的所有有循环节的前缀(循环节数量>1)
大致思路:
首先来一个奇妙的结论:如果1-x有循环,那么x-next[x]为循环节长度。next数组即为KMP算法中的next数组。
根据这个结论很容易写出代码,我就不赘述了。
(我才不会说我不会证明这个结论)
代码:
#include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <vector> #include <ctime> #include <map> #include <stack> #include <queue> #include <cstring> #include <algorithm> using namespace std; #define sacnf scanf #define scnaf scanf #define maxn 1000010 #define maxm 26 #define inf 1061109567 #define Eps 0.00001 const double PI=acos(-1.0); #define mod 7 #define MAXNUM 10000 void Swap(int &a,int &b) {int t=a;a=b;b=t;} int Abs(int x) {return (x<0)?-x:x;} typedef long long ll; typedef unsigned int uint; char s[maxn]; int f[maxn]; void Get_next(int len) { int i=0,j=-1;f[0]=-1; while(i<len) { if(j==-1||s[i]==s[j]) { i++;j++;f[i]=j; if(i%(i-j)==0&&i>1&&j!=0) printf("%d %d ",i,i/(i-j)); } else j=f[j]; } } int main() { //freopen("data.in","r",stdin); //freopen("data.out","w",stdout); //clock_t st=clock(); int len,kase=1; while(~scanf("%d",&len)) { if(len==0) break; printf("Test case #%d ",kase++); scanf("%s",s); Get_next(len); //for(int i=0;i<len;i++) printf("%d ",i-f[i]); printf(" "); } //clock_t ed=clock(); //printf(" Time Used : %.5lf Ms. ",(double)(ed-st)/CLOCKS_PER_SEC); return 0; }