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
题目类型：简单字符处理
算法分析：周期变量zhouqi从1开始枚举到字符串的长度len，其中舍去判断不能被len整除的zhouqi。对于可能为最小周期的zhouqi使用求余的方法进行判断。注意本题最后一组数据的输出之后是没有空行的，下面第一个代码是更好的实现
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 |
/************************************************** filename :j.cpp author :maksyuki created time :2017/12/2 10:02:00 last modified :2017/12/2 10:19:40 file location :C:\Users\abcd\Desktop\TheEternalPoet ***************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("in", "r", stdin) #define CFO freopen ("out", "w", stdout) #define CPPFF ifstream cin ("in") #define CPPFO ofstream cout ("out") #define DB(ccc) cout << #ccc << " = " << ccc << endl #define DBT printf("time used: %.2lfs\n", (double) clock() / CLOCKS_PER_SEC) #define PB push_back #define MP(A, B) make_pair(A, B) typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef pair <int, int> PII; typedef pair <int, bool> PIB; const int INF = 0x7F7F7F7F; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 1e5 + 6666; char s[maxn], v[maxn], tmp[maxn]; int main() { #ifdef LOCAL CFF; //CFO; #endif int t, id = 1; scanf("%d", &t); while(t--) { scanf("%s", s); int len = strlen(s); int minval = len; for(int i = 1; i < len; i++) { if(len % i) continue; strncpy(v, s, i); v[i] = 0; strcpy(tmp, v); bool is_find = true; char *p = NULL; int len2 = len / i; for(int j = 1; j <= len2; j++) { p = strstr(s, tmp); strcat(tmp, v); if(p == NULL) { is_find = false; break; } } if(is_find) { minval = i; break; } } if(id++ > 1) puts(""); printf("%d\n", minval); } return 0; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
#include <cstdio> #include <iostream> #include <fstream> #include <cstring> using namespace std; const int maxn = 86; char a[maxn]; int main() { int cases; //ifstream cin ("aaa.txt"); cin >> cases; while (cases--) { cin >> a; int len = strlen (a); int zhouqi, i; bool isend = false; for (zhouqi = 1; !isend; zhouqi++) { if (len % zhouqi == 0) { for (i = 0; a[i]; i++) { if (a[i] != a[(i+zhouqi)%len]) break; } } if (i == len) isend = true; } if (cases) printf ("%d\n\n", --zhouqi); else printf ("%d\n", --zhouqi); } return 0; } |
- « 上一篇：uva401
- uva678：下一篇 »