【C++】文字列の回転判定：一方の文字列が他方の回転かどうかをチェックする方法

問題概要

2つの文字列 s と t が与えられたとき、s を回転（rotate）させることで t を作り出せるかどうか、つまり s が t の回転になっているかを判定します。

例えば、入力が s = "helloworld"、t = "worldhello" の場合を見てみましょう。s を適切な位置で分割して前後を入れ替えると t が得られるため、出力は True（1） になります。

解法のアプローチ

この問題は、以下の手順でシンプルかつ効率的に解くことができます。

• まず、s0 と s1 の長さが異なる場合は回転になり得ないため、false を返します。

• s0 を自分自身と連結した文字列 s = s0 + s0 を作成します。

• s1 が s に含まれているかを判定し、含まれていれば true、そうでなければ false を返します。

このテクニックが機能する理由は、s0 + s0 という文字列の中に s0 のすべての回転パターンが部分文字列として含まれるからです。実際、"helloworld" を2回連結すると "helloworldhelloworld" となり、その中に "worldhello" が含まれていることが確認できます。

実装例（C++）

それでは、実際のコードを見て理解を深めましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    bool solve(string s0, string s1) {
        if(s0.size() != s1.size())
        return false;
        string s = s0 + s0;
        return s.find(s1) != string::npos;
    }
};
int main(){
    Solution ob;
    cout << (ob.solve("helloworld", "worldhello"));
}

入力

"helloworld", "worldhello"

出力

1

コードのポイント

• string::find() は部分文字列を検索する標準ライブラリ関数で、見つからなかった場合に string::npos を返します。これを利用することで、回転の有無を1行で判定できます。

• 長さの事前チェックにより、無駄な連結や検索処理を回避でき、処理が高速化されます。

• この手法の時間計算量は O(n)、空間計算量も連結した文字列の分だけ O(n) となります。