abc145_b atcoder

ABC145 B - Echo

ABC145 B - Echo
Feb. 2, 2020, 1:52 p.m.

目次

問題

https://atcoder.jp/contests/abc145/tasks/abc145_b

文字列$S$が与えられて、$S$がある文字列の完全な繰り返しになっているかを判定する問題です.

解説

完全な繰り返しなので、$S$の長さが奇数の場合にはありえないのでNoです.
偶数の場合には$S$を真ん中で区切ってその前半と後半の文字列を1文字ずつ比較してすべての文字が同じであればYesとなります.

計算量

文字列を半分にして全文字比較する必要があるので、

$$
O(N / 2)
$$

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
Int N;
string S;

void input() {
  cin >> N >> S;
}

void solve() {
  if (N % 2 == 1) {
    cout << "No" << endl;
    return;
  }

  if (S.substr(0, N/2) == S.substr(N/2)) cout << "Yes" << endl;
  else cout << "No" << endl;
}

int main(void) {
  input();
  solve();
  return 0;
}