CPE 一顆星
題目連結:https://zerojudge.tw/ShowProblem?problemid=e537
內容
如果一個字串可以通過將另一個長度為k的字串的一個或多個重複連接起來而形成，則它被稱為period k。
例如，字串”abcabcabcabc”具有period 3，因為它由字串”abc”的4個重複組成。
它還具有period 6 (兩個重複的”abcabc”)和period 12 (一個重複的”abcabcabcabc”)。
輸入第一列有一個整數 N 代表測資數，每筆測資第一列為一個空白，第二列為字串 s (s長度 <= 80)。
輸出最小的 period，兩個連續輸出由空白列分開。
範例輸入
1
HoHoHo
範例輸出
2
想法
可能的解為字串長度的因數，因此只要取因數由小到大判斷是否成立即可。
若長度為1就直接輸出1。
程式碼
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
| #include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false), cin.tie(nullptr)
using namespace std;
int main(){
fastio;
int N, len, ans;
string s;
bool suc;
cin >> N;
while(N--){
cin >> s;
len = s.length();
if(len == 1){
cout << "1\n";
if(N != 0) cout << "\n";
continue;
}
for(int c = 1; c <= len/2; ++c){
suc = true;
if(!(len % c)){
for(int i = 0; i < c; ++i){
for(int j = i; j < len; j += c){
if(s[i] != s[j]){
suc = false;
break;
}
}
if(!suc) break;
}
if(suc){
cout << c << "\n";
break;
}
}
if(c == len/2) cout << len << "\n";
}
if(N != 0) cout << "\n";
}
return 0;
}
|