问题描述
p455原题链接：UVaOJ 455 - Periodic Strings
相关说明：本题为《算法竞赛入门经典（第2版）》习题 3-4
解法一：模拟
暴力枚举求解，假设周期长度为 1, 2 ... 递增地进行验证（注意满足条件的 k 一定能被字符串 s 的长度整除）。验证的思路也很简单，从 pos=k 开始对比，如果找到 s[pos] != s[pos % k] 这样的反例，则当前的 k 不能作为周期长度，继续验证下一个 k 值。
|
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 |
#include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; while (n--) { string s, blank; getline(cin, blank); cin >> s; for (int k = 1; k <= s.length(); ++k) { if (s.length() % k) continue; bool repeat = true; for (int pos = k; pos < s.length(); ++pos) { if (s[pos] != s[pos % k]) { repeat = false; break; } } if (repeat) { cout << k << endl << (n ? "\n" : ""); break; } } } return 0; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
n = int(input()) for i in range(n): input() s = input() for k in range(1, len(s) + 1): if len(s) % k == 0: repeat = True for pos in range(k, len(s)): if s[pos] != s[pos % k]: repeat = False break if repeat: print("{}{}".format(k, "\n" if i < n - 1 else "")) break |
