UVa455 周期串 习题3-4

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;
}

*/