辞書式順序で最小となる文字列回転の求め方【C++実装例つき】

文字列とは、複数の文字が並んだシーケンス（列）のことです。辞書式順序での回転（Lexicographical Rotation）とは、文字列をさまざまな位置で回転させたときに、その結果が辞書式順序（辞書に載るような五十音・アルファベット順）で最も小さくなるような回転を求める問題です。

この問題の解法は非常にシンプルです。まず、与えられた文字列をそれ自身と連結して一時的な文字列を作ります。次に、連結後の文字列から長さ分ずつ切り出すことで、すべての回転パターンを配列に格納します。最後にこの配列を昇順にソートすれば、先頭の要素（最小値）が求める答えになります。

入力と出力

Input:
文字列 “BCAAFAABCD”
Output:
回転後の文字列: “AABCDBCAAF”

元の文字列 “BCAAFAABCD” を1文字ずつ回転させると複数の候補が生まれますが、その中で辞書式順序が最小になるのは “AABCDBCAAF” です。

アルゴリズム

minStrRotation(str)

入力 − 与えられた文字列。

出力 − 辞書式順序で最小となる回転文字列。

Begin
   n := 文字列 str の長さ
   すべての回転を格納するための配列 strArr を定義する
   tempStr := str を2回連結した文字列とする

   for i := 0 to n-1, do
      strArr[i] := tempStr の i 番目から n 文字分の部分文字列
   done

   strArr を昇順にソートする
   return strArr[0]
End

C++による実装例

#include <iostream>
#include <algorithm>
using namespace std;

string minStrRotation(string str) {
   int n = str.size();
   string strArray[n];    // 全ての回転を格納する配列
   string tempStr = str + str;    // 文字列を2回連結する

   for (int i = 0; i < n; i++)
      strArray[i] = tempStr.substr(i, n);    // i番目からn文字分の部分文字列を取得
   sort(strArray, strArray+n);
   return strArray[0];    // 先頭要素（最小値）が結果
}

int main() {
   string str;
   cout << "Enter String: "; cin >> str;
   cout << "Rotated String: " << minStrRotation(str);
}

実行結果

Enter String: BCAAFAABCD
Rotated String: AABCDBCAAF

計算量について

この方法では、回転パターンの生成に O(n)、ソートには各要素の比較に最大 O(n) かかるため、全体の計算量は O(n² log n) となります。文字数が少ない場合は十分実用的ですが、より大規模な文字列に対しては、Booth のアルゴリズムなど O(n) で最小回転を求める手法が知られています。