C++で元の文字列と一致するまでに必要な最小回転数を求める方法

問題概要

文字列が与えられたとき、その文字列を回転させて元の文字列と完全に一致させるために必要な最小の回転回数を求めるのが、この問題の目的です。

例

たとえば、入力文字列が「bbbbb」の場合、必要な最小回転数は 1 です。1回転させるだけで元の文字列と一致するためです。

アルゴリズム

この問題は、元の文字列を2回連結した文字列（自己連結文字列）を利用することで、効率的に解くことができます。手順は以下のとおりです。

1. 結果を格納する変数 result = 0 で初期化する
2. 元の文字列を2回連結した一時文字列 temp を作成する
3. temp の先頭から1文字目（インデックス1）以降について、元の文字列と同じ長さの部分文字列を取り出す
4. カウンタをインクリメントする
5. 取り出した部分文字列が元の文字列と一致するか確認する。一致すればループを抜ける。一致しなければ次のインデックスから手順2以降を繰り返す

実装例（C++）

#include <bits/stdc++.h>
using namespace std;
int getRotationCount(string str) {
    string temp = str + str;
    int n = str.length();
    for (int i = 1; i <= n; ++i) {
        string sub = temp.substr(i, str.size());
        if (str == sub) {
            return i;
        }
    }
    return n;
}
int main() {
    string str = "bbbbb";
    cout << "Rotation count = " << getRotationCount(str) <<
    endl;
    return 0;
}

コードのポイント

• 自己連結の活用： 文字列を2回連結すると、その中にすべての回転パターンが部分文字列として含まれます。これにより、実際に文字列を回転させる操作を省略できます。
• 計算量： 各インデックスで部分文字列の比較を行うため、計算量は O(n²) となります。
• 戻り値： ループ内で一致が見つからない場合（すべての回転が異なる場合）は、文字列の長さ n を返します。

実行結果

上記のプログラムをコンパイルして実行すると、次の出力が得られます。

Rotation count = 1

このように、自己連結文字列と部分文字列の比較を組み合わせることで、最小回転数をシンプルかつ効率的に求めることができます。