3-4 周期串(Periodic Strings, UVa455)

455 - Periodic Strings

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