3-4 「UVa455」周期串:
如果一个字符可以由某个长度为k的字符串重复多次得到,则称该串以k为周期。例如:abcabcabcabc 以3为周期(注意:它也以6和12为周期)输入一个长度不超过80的字符串,输出其最小周期。
代码
#include<stdio.h>
#include<string.h>
#define N 80 //暴力枚举法
int check(int k,int n,char *s)
{
int result=1,i,j;
for(i=0;i<k;i++){ //对于第一个循环内的数来说
for(j=i+k;j<n;j+=k){ //比较后面所有循环组内的数
if(s[i]!=s[j]) //若有一次不相同就返回0 (注意通常选择判断不相同的情况)
return 0;
}
}
return result;
}
int main()
{
int i,k,t;
char str[N];
scanf("%d",&t);
getchar();
while(t--){
scanf("%s",str);
for(i=1;i<=strlen(str);i++){ //枚举所有的周期。周期i的范围
if(strlen(str)%i==0){ //大前提,长度是周期的倍数
if(check(i,strlen(str),str)){ //小前提能构成循环 ,i渐渐增大,直到增大到满足循环条件就停止
k=i;
break;
}
}
}
printf("%d\n",k);
if(t) printf("\n");
}
return 0;
}
/* //别人的代码
#include<stdio.h>
#include<string.h>
int main()
{
char s[105];
int len, i,j,t;
scanf("%d", &t);
while (t--)
{
scanf("%s", s);
n = strlen(s);
for (i = 1; i <= len; i++) //i作为周期数的范围,i从1到n中寻找最小周期数
if (len %i == 0) //先判断是否能整除i,减小运算量
{
for (j = i; j < len; j++) //如果第一周期与第二周期所对应的数不相等,break跳出循环,i++
if (s[j] != s[j%i])
break;
if (j ==len) //如果完全相等,j将等于len,这时输出i的值即为最小周期数
{
printf("%d\n", i);
if(t) printf("\n"); // 题目要求答案隔行输出
break; //用break跳出循环,达到最小这一隐含条件
}
}
}
return 0;
}
*/