周期串Uva455 P37 3-4
阿里云国内75折 回扣 微信号:monov8 |
阿里云国际,腾讯云国际,低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号:monov8 飞机:@monov6 |
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
最开始以为是求出现次数最小的那个字符;
后来想一想是真的不对;
然后看着数据不大, 就用暴力枚举的方法;
求出最小的周期,那么就是从最小的开始枚举,也就是长度为1, 再judge;
#include<bits/stdc++.h>
#define clr(x) memset(x, 0, sizeof(x)) #define LL long long using namespace std; const int INF = 0x3f3f3f3f; const int maxn = ; char str[]; char s[]; int main() { int T; cin >> T; while(T--) { clr(str); cin >> str; int len = strlen(str); for(int i = ; i < len; i++) { if(len % (i+) != ) continue; int cnt = , flag = ; clr(s); for(int j = ; j <= i; j++ ) { s[cnt++] = str[j]; } //puts(s); int tmp = i + ; for(int k = ; k < len / (i + ) - ; k++) { for(int l = ; l < cnt; l++) { //printf("%c %c\n", s[l], str[tmp]); if(s[l] != str[tmp++]) { flag = ; break; } } } if(flag) { cout << i + << endl; if(T) cout << endl; break; } //puts("_________"); } } return ; }
阿里云国内75折 回扣 微信号:monov8 |
阿里云国际,腾讯云国际,低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号:monov8 飞机:@monov6 |