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