UVa455 - Periodic Strings

  

   

    

     

    
    

     

      //UVa455 - Periodic Strings
     
    
   

    

     

    
    

     

      //题目：求一个串的最小循环节。
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      #define A1 //直接枚举 O(N*N) 已经AC
     
    
   

    

     

    
    

     

      #define A2 //旧代码，WA
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      #ifdef A1
     
    
   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      int main(){
     
    
   

    

     

    
    

     
	//freopen("data.in","r",stdin);
     
    
   

    

     

    
    

     
	char s[100];
     
    
   

    

     

    
    

     
	int n;
     
    
   

    

     

    
    

     
	scanf("%d",&n);
     
    
   

    

     

    
    

     
	while(n--){
     
    
   

    

     

    
    

     
		scanf("%s",s);
     
    
   

    

     

    
    

     
		int len = strlen(s);
     
    
   

    

     

    
    

     
		for(int j, i = 1; i <= len; i++) if(len%i == 0){
     
    
   

    

     

    
    

     
			for(j = i; j < len; j++) if(s[j] != s[j%i]) break;
     
    
   

    

     

    
    

     
			if(j == len){ printf("%d\n",i); break;}
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
		if(n)printf("\n");
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	return 0;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      #endif 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      #ifdef A2
     
    
   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      int main(){
     
    
   

    

     

    
    

     
	//freopen("data.in","r",stdin);
     
    
   

    

     

    
    

     
	int T;
     
    
   

    

     

    
    

     
	scanf("%d",&T);
     
    
   

    

     

    
    

     
	while(T--){
     
    
   

    

     

    
    

     
		char s[85];
     
    
   

    

     

    
    

     
		int len,is=0;
     
    
   

    

     

    
    

     
		scanf("%s",s);
     
    
   

    

     

    
    

     

      		len = strlen(s);
     
    
   

    

     

    
    

     
		for(int i = 1; i <= len/2; i++){//i为周期，周期长小于一半的字符串长
     
    
   

    

     

    
    

     
			if(len%i == 0){//字符串长度为循环节整数倍
     
    
   

    

     

    
    

     

      				is=1;//开关
     
    
   

    

     

    
    

     
				for(int j =1;j < len/i; j++)//字符串中的第j个对应周期的首元素是否相等
     
    
   

    

     

    
    

     
					for(int l = 0; l < i; l++)//字符串中的第j个对应周期的第i个元素是否相等
     
    
   

    

     

    
    

     
						if(s[l] != s[j*i+l]){is=0;break;}
     
    
   

    

     

    
    

     

      			}
     
    
   

    

     

    
    

     
			if(is){printf("%d\n",i);break;}
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
		if(!is)printf("%d\n\n",0);
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	return 0;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      //测试数据：abcabcabc len=2
     
    
   

    

     

    
    

     

      //测试数据：acadacad len=4
     
    
   

    

     

    
    

     

      //测试数据：acacac len=2
     
    
   

    

     

    
    

     

      //测试数据：aaaaaa len=1
     
    
   

    

     

    
    

     

      #endif 
     
    
  
 

  
 
 

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/54744429