C++で同じ文字列を取得するために必要な最小回転

問題の説明

文字列が与えられた場合、同じ文字列を取得するために必要な最小回転数を見つける必要があります

例

入力文字列が「bbbbb」の場合、最低1回転が必要です

アルゴリズム

1. Initialize result = 0
2. Make a temporary string equals to original string concatenated with itself.
3. Take the substring of temporary string of size same as original string starting from second character i.e. index 1
4. Increment the counter
5. Check whether the substring becomes equal to original string. If yes, then break the loop. Else go to step 2 and repeat it from the next index

例

#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;
}

上記のプログラムをコンパイルして実行する場合。次の出力を生成します

出力

Rotation count = 1