周期串Uva455 P37 3-4

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

HoHoHo

Sample Output

最开始以为是求出现次数最小的那个字符；

后来想一想是真的不对；

然后看着数据不大，就用暴力枚举的方法；

求出最小的周期，那么就是从最小的开始枚举，也就是长度为1，再judge；

  1 #include<bits/stdc++.h>
  2 #define clr(x) memset(x, 0, sizeof(x))
  3 
  4 #define LL long long
  5 
  6 using namespace std;
  7 
  8 const int INF = 0x3f3f3f3f;
  9 
 10 const int maxn = 100005;
 11 
 12 char str[1005];
 13 
 14 char s[1005];
 15 
 16 int main()
 17 
 18 {
 19 
 20 int T;
 21 
 22 cin >> T;
 23 
 24 while(T--)
 25 
 26 {
 27 
 28 clr(str);
 29 
 30 cin >> str;
 31 
 32 int len = strlen(str);
 33 
 34 for(int i = 0; i < len; i++)
 35 
 36 {
 37 
 38 if(len % (i+1) != 0)
 39 
 40 continue;
 41 
 42 int cnt = 0, flag = 1; clr(s);
 43 
 44 for(int j = 0; j <= i; j++ )
 45 
 46 {
 47 
 48 s[cnt++] = str[j];
 49 
 50 }
 51 
 52 //puts(s);
 53 
 54 int tmp = i + 1;
 55 
 56 for(int k = 0; k < len / (i + 1) - 1; k++)
 57 
 58 {
 59 
 60 for(int l = 0; l < cnt; l++)
 61 
 62 {
 63 
 64 //printf("%c %c
", s[l], str[tmp]);
 65 
 66 if(s[l] != str[tmp++])
 67 
 68 {
 69 
 70 flag = 0;
 71 
 72 break;
 73 
 74 }
 75 
 76 }
 77 
 78 }
 79 
 80 if(flag)
 81 
 82 {
 83 
 84 cout << i + 1 << endl;
 85 
 86 if(T)
 87 
 88 cout << endl;
 89 
 90 break;
 91 
 92 }
 93 
 94 //puts("_________");
 95 
 96 }
 97 
 98 }
 99 
100 return 0;
101 
102 }