辞書式順序で最小の文字列回転

解決策は単純です。指定された文字列をそれ自体と連結するだけで、別の配列に文字列のすべての回転が格納されます。その後、配列を昇順で並べ替えると、最小値が最終結果になります。

入力と出力

Input:
The String “BCAAFAABCD”
Output:
Rotated String: “AABCDBCAAF”

アルゴリズム

minStrRotation(str)

入力- 指定された文字列。

出力- 最小限の弦の回転が必要です。

Begin
   n := length of str
   define strArr to store all rotations
   tempStr := concatenate str with str again

   for i := 0 to n, do
      strArr[i] := substring of tempStr from (i to n)
   done

   sort the strArr
   return strArr[0]
End

例

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

string minStrRotation(string str) {
   int n = str.size();
   string strArray[n];    //array to store all rotations of str
   string tempStr = str + str;    //concatinate str two times

   for (int i = 0; i < n; i++)
      strArray[i] = tempStr.substr(i, n);    //get sub string from ith index to nth index
   sort(strArray, strArray+n);
   return strArray[0];    //The first index is the result
}

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

出力

Enter String: BCAAFAABCD
Rotated String: AABCDBCAAF