C++で全ての文字列を一致させるための最小移動回数を求める方法

問題の概要

互いに回転（順列）の関係にある n 個の文字列が与えられます。使用できる操作は「任意の文字列の先頭の1文字を取り出し、その文字列の末尾へ移動する」ことだけです。この操作を繰り返してすべての文字列を同一にするとき、必要となる最小の操作回数を求めます。

例

arr[] = {"abcd", "cdab"} の場合、必要な移動回数は 2 回です。

• 最初の文字列 "abcd" に対して、文字 'a' を末尾へ移動します。操作後の文字列は "bcda" になります。
• 次に、文字 'b' を末尾へ移動します。操作後の文字列は "cdab" となり、2番目の文字列と一致します。

アルゴリズム

1. 基準となる文字列を1つ選びます（ここでは str1 と呼びます）。
2. str1 を2回連結した一時文字列を作成します。
   temp = str1 + str1
3. temp の中で他の各文字列を検索し、見つかった位置（インデックス）がその文字列に必要な回転回数になります。
4. すべての文字列を基準として上記の手順を繰り返し、得られた回数の中で最も小さい値を答えとして返します。

この手法が成り立つのは、「文字列 s を2回連結した s + s の中には、s のすべての回転パターンが必ず含まれる」という性質があるためです。

C++での実装例

#include <iostream>
#include <string>
#include <algorithm>
#include <climits>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;

int minMoves(string str[], int n) {
    int minCnt = INT_MAX;
    // 各文字列を「目標」として順に試す
    for (int i = 0; i < n; ++i) {
        int cnt = 0;
        for (int j = 0; j < n; ++j) {
            string temp = str[j] + str[j];
            int index = temp.find(str[i]);
            if (index != string::npos) {
                cnt += index; // 必要な回転回数を加算
            }
        }
        minCnt = min(cnt, minCnt);
    }
    return minCnt;
}

int main() {
    string str[] = {"abcd", "cdab", "bacd", "cdba"};
    cout << "Minimum moves: " << minMoves(str, SIZE(str)) << endl;
    return 0;
}

実行結果

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

Minimum moves: 2

計算量について

文字列の数を n、文字列の長さを L とすると、すべての文字列のペアに対して部分文字列検索（find）を行うため、時間計算量は O(n² × L) となります。文字列の数や長さが大きい場合は注意が必要ですが、問題の規模が小さい範囲では十分に実用的なアプローチです。