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