AtCoder ABC 230 B - Triple Metre (6Q, 灰色, 200 点)

実は愚直に文字列 を作っても解ける！

• 問題へのリンク

問題概要

文字列 を、"oxx" を 個連結した文字列とする。

与えられた文字列 が、 の部分文字列であるかどうかを判定せよ。

制約

• 

考えたこと

一般に、文字列 が文字列 を部分文字列にもつかどうかは次のように判定できる。

---

のいずれかに対して、

の 文字目から 文字分を切り取った部分文字列が に等しい

---

今回の問題も同様にすればよい。つまり、"oxx" を 個連結した文字列 を作り、上記のことをすればよい。

もう少し効率化

上記の解法でも十分だが、もう少し効率化してみよう。まず、 の周期性から、次のいずれかを満たすかどうかを判定するだけで十分であるといえる！

---

• の 0 文字目から 文字分を切り取った部分文字列が に等しい
• の 1 文字目から 文字分を切り取った部分文字列が に等しい
• の 2 文字目から 文字分を切り取った部分文字列が に等しい

---

さらに、こうなれば、文字列 の長さは もある必要がない。 よりも少し長い程度で十分だ。

具体的には、 は "oxx" を 4 個連結したものであれば十分だ。

以上の解法を実装すると、下のコードのようになる。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    string S, T;
    cin >> S;
    for (int i = 0; i < 4; i++) T += "oxx";

    bool res = false;
    for (int i = 0; i < 3; i++) {
        if (T.substr(i, S.size()) == S) res = true;
    }

    cout << (res ? "Yes" : "No") << endl;
}