http://poj.org/problem?id=1961
判断某一字符串中 , 哪些前缀子串有周期 , 输出子串长度以及子串中周期重复的次数 ( 次数>1 )
需要的只是对KMP性质的进一步理解...代码很短如下
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 #include<cmath> 6 #include<queue> 7 using namespace std; 8 const int maxn=1000010; 9 const double eps=1e-8; 10 const long long modn=1000; 11 char a[maxn]={}; 12 int nex[maxn]={}; 13 int size[maxn]={}; 14 int n,m; 15 void doit(){ 16 int j=-1,i=0; 17 nex[0]=-1; 18 int z; 19 while(i<n){ 20 if(j==-1||a[j]==a[i]){ 21 nex[++i]=++j; 22 if(i%(i-j)==0&&i/(i-j)>1){ 23 printf("%d %d ",i,i/(i-j)); 24 } 25 }else{ 26 j=nex[j]; 27 } 28 } 29 } 30 int main(){ 31 int K=0; 32 while(~scanf("%d",&n)&&n!=0){ 33 ++K; 34 memset(nex,0,sizeof(nex)); 35 memset(size,0,sizeof(size)); 36 scanf("%s",a); 37 printf("Test case #%d ",K); 38 doit(); 39 cout<<endl; 40 } 41 return 0; 42 }