习题3-4 周期串(Periodic Strings, UVa455)
如果一个字符串可以由某个长度为k的字符串重复多次得到,则称该串以k为周期。例 如,abcabcabcabc以3为周期(注意,它也以6和12为周期)。
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#define MAXN 85
int main(){
int T=0,first=1;
char a[MAXN];
scanf("%d",&T);
while(T--){
int n,p,k,match=1;
scanf("%s",a);
n = strlen(a);
if(!first) printf("\n");
if (first) first = 0;
for(k = 1;k <= n;k++){
if (n%k==0){
p = n/k; //若k为候选周期，p为重复字串数
for (int j=0;j<k;j++){
for (int m=1;m<p;m++){
if (a[j] == a[j+k*m]) {
match = 1;
continue;
}
else {
match = 0;
break;
}
}
if (!match) break;
}
}
if (match) {
printf("%d\n",k);
break;
}
else continue;
}
if (!match) printf("%d\n",n);
}
return 0;
}
