MEGChai MEGChai
  • 文章
    • 随笔
    • 笔记
    • 教程
  • 关于
首页 › 数据结构与算法 › 在线评测 › UVaOJ 455 - Periodic Strings
AOAPC II

UVaOJ 455 - Periodic Strings

Chai
2021-11-24 0:00:00在线评测阅读 223

问题描述

p455

原题链接:UVaOJ 455 - Periodic Strings

相关说明:本题为《算法竞赛入门经典(第2版)》习题 3-4

解法一:模拟

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

C++
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;
}
Python
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
AOAPC II UVaOJ 字符串
赞赏 赞(0)
订阅
提醒
guest
guest
0 评论
内嵌评论
查看所有评论
  • 0
  • 0
Copyright © 2020-2023 MEGChai.
  • 文章
    • 随笔
    • 笔记
    • 教程
  • 关于
# 生活 # # 心理 # # 编程 # # 音乐 # # 写作 #
Chai
95
文章
4
评论
58
喜欢
wpDiscuz