ITP1_8_D リングをC++で解いてみた[AIZU ONLINE JUDGE]

こんにちは！ mnbd（@mnbbbbbd）です。

AIZU ONLINE JUDGEの「ITP1_8_C リング」を解いてみましたので、その回答と解説をご紹介いたします。

プログラミング初心者なので、もっといい回答があるに違いありません。

あくまでも「動作はする」サンプルとしてご覧ください。

問題文
回答
解説
ハマったポイント
学んだこと
まとめ

問題文

図のようなリング状の文字列 s の任意の位置から、時計回りに連続した文字をいくつか選んで、文字列 p が作れるかを判定するプログラムを作成してください。
１行目に文字列 $s$ が与えられます。２行目に文字列 $p$ が与えられます。
$p$ が作れる場合は Yes と、作れない場合は No と１行に出力してください。
https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/8/ITP1_8_D

このページでは、図を表示していません。問題文の引用元リンクには図が表示されていますので、必要な方はそちらのページを参照してください。

ざっくり言って、「文字列をリング状につなげてる」と解釈していいと思います。

回答

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

int main() {
    string s;
    cin >> s;
    s += s;
    string p;
    cin >> p;

    string::size_type pos = s.find(p);
    if(pos == string::npos) {
        cout << "No" << endl;
    } else {
        cout << "Yes" << endl;
    }

    return 0;
}

解説

文字列をリング状にするために、入力で取得した文字列の後ろに同じ文字列を連結しています。

変数sの中に変数pの文字列が含まれるかどうかをfind()関数を実行しています。

find()関数では、文字列が含まれる時にその位置を返し、含まれない時にstring::nposを返しますので、出力形式に則った形で表示しています。

ハマったポイント

リング状とのことで、一度終端まで行った文字列をまた最初に戻って判定する必要がありますが、その処理の書き方がわかりませんでした。

他の方の回答を拝見させていただき、同じ文字列を最後尾に追加することでリング状としているのを知りました。

これは自分には思いつかなかった考えでした。

また、単純に変数sの中に変数pの文字列があるかどうかを判定するプログラムの書き方もわかりませんでした。

これはstring型のfind関数を使えばいいのですが、一から書くとどうかけばいいのか、というのは課題です。

学んだこと

ハマったポイントと重複しますが、リング状にする文字列の処理は、もう一つ同じ文字列を最後尾に追加するということ。これは目からウロコでした。

まとめ

AIZU ONLINE JUDGEの「ITP1_8_C 文字のカウント」の回答と解説をご紹介いたしました。

私はまだ初心者ですが、よかったら一緒に勉強していきましょう。

Twitter（@mnbbbbbd）などをフォローしていただければ幸いです。

以上です。
読んでいただきありがとうございました。