UVaOJ 455 - Periodic Strings

问题描述

解法一：模拟

暴力枚举求解，假设周期长度为 1, 2 ... 递增地进行验证（注意满足条件的 k 一定能被字符串 s 的长度整除）。验证的思路也很简单，从 pos=k 开始对比，如果找到 s[pos] != s[pos % k] 这样的反例，则当前的 k 不能作为周期长度，继续验证下一个 k 值。

#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;
}

#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;

}

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

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

AOAPC II UVaOJ 字符串