void_cpp1 于 2016.03.23 13:03 提问

Periodic Strings
A character string is said to have period k if it can be formed by concatenating one or more repetitions of another string of length k. For example, the string "abcabcabcabc" has period 3, since it is formed by 4 repetitions of the string "abc". It also has periods 6 (two repetitions of "abcabc") and 12 (one repetition of "abcabcabcabc").

Write a program to read a character string and determine its smallest period.

Input

The first line oif the input file will contain a single integer N indicating how many test case that your program will test followed by a blank line. Each test case will contain a single character string of up to 80 non-blank characters. Two consecutive input will separated by a blank line.

Output

An integer denoting the smallest period of the input string for each input. Two consecutive output are separated by a blank line.

Sample Input

1

HoHoHo
Sample Output

2

`````` //要多注意细节，多考虑极端情况（注意循环字符中还有相同字符的情况!!!）
#include <stdio.h>
#include <string.h>
int main()
{
int T,len,i,k,temp,first=1;//T代表测试块的个数,len是字符串长度,temp存储可能的周期值
char str[90]={0};//存储字符串
scanf("%d",&T);
while(T--){
temp=0,k=0;
scanf("%s",str);
len=strlen(str);
for(i=1;i<len;i++){
if(str[i]==str[0]){
temp=i;
for(k=0;k<temp;k++,i++){
if(str[k]!=str[i]){//反向思维，针对ABABACC的情况
temp=0;
i--;
break;
}
if(k!=temp-1&&i==len-1){//主要针对ABCDAB的情况
temp=0;
break;
}
if((k==temp-1)&&(i!=len-1))
k=-1;//始终注意k的自加
}
}
}
if(i==len&&!k)//注意不存在周期的情况！
temp=0;
if(first){
printf("%d\n",temp);
first=0;
}
else
printf("\n%d\n",temp);
}
return 0;
}

``````

1个回答

leilba   2016.03.23 13:50

leilba 回复明知道这是一场意外: 哈哈，能ac就好

void_cpp1 回复林深: 哈哈改了一下就AC了，谢谢

void_cpp1 回复林深: 哈哈改了一下就AC了，谢谢

void_cpp1 回复林深: 好吧，刚才试了一下，果然会错了意

leilba 回复明知道这是一场意外: 这个题找的是最小重复单位呀，当全部不一样的时候就只能是本身了呀

void_cpp1 回复林深: 这个不应该是没有周期的情况么，难道我会错了题意