Period(sdut2476)

[题目大意]：给定一个字符串，求到哪一位时的字串是前几位循环组成的，并求出循环次数。

思路：求每个前缀的最小循环周：从i到n枚举len，如果len%(len-next[len])==0，则这个前缀是由循环节组成的，且循环次数为len/(len-next[len])//len为当前i的值，next[len]为当前j的值。
#include <stdio.h>

#include <string.h>

#include <stdlib.h>

char a[1000001];

int next[1000001];

int n;

void  Getnext()

 {
    
      int i=0;
   
      int j=-1;
  
      next[0]=-1;
 
     while(i<n)

     {
    
        if(j==-1||a[i]==a[j])
   
       {
           
         i++;
        
         j++;
          
         next[i]=j;
        
        if(i%(i-next[i])==0&&i/(i-next[i])>1)

         {
              
            printf("%d %d\n",i,i/(i-next[i]));
     
         }
      
        }
     
        else j=next[j];
 
   }

}

int main()

{
   
   int k=0;
   
   while(scanf("%d",&n)!=EOF)
 
   {
        
     k++;
        
     if(n==0) break;
      
     getchar();
      
     for(int i=0;i<n;i++)
     
       scanf("%c",&a[i]);
      
    printf("Test case #%d\n",k);
    
     Getnext();
       
    printf("\n");
   
  }
  
  return 0;

}

Period(sdut2476),布布扣,bubuko.com

Period(sdut2476)

原文：http://www.cnblogs.com/zhangmingcheng/p/3793400.html