UVA - 455
| Time Limit:3000MS | Memory Limit:Unknown | 64bit IO Format:%lld & %llu |
Description
| 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 lengthk. 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.
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.
An integer denoting the smallest period of the input string for each input. Two consecutive output are separated by a blank line.
1 HoHoHo
2
1.枚举字符串长度的约数i，判断是否为周期
2.若是，输出i；否则i++，继续判断
本题输出格式比较坑
1 #include <iostream> 2 #include <cstring> 3 4 using namespace std; 5 6 int period(int p, int n, char* a) 7 { //判断周期 8 for(int i = 0; i < n - p; i++) 9 { 10 if(a[i] != a[i+p]) 11 return 0; //不是周期，返回0 12 } 13 return p; 14 } 15 int main() 16 { 17 int num,first = 0; 18 char a[110]; 19 cin >> num; 20 //接收回车符，防止被cin.getline读取 21 while(num--) 22 { 23 cin >> a; 24 int len = strlen(a), p = 0; 25 for(int i = 1; i <= len; i++) 26 { 27 if(len%i == 0) 28 {p = i; 29 if(period(p,len,a)) 30 break; 31 } 32 } 33 if(first) cout << endl << p << endl; 34 else
35 {cout << p << endl;first =1;} 36 } 37 return 0; 38 }
原文：http://www.cnblogs.com/ekinzhang/p/4280082.html