Số lần quay tối thiểu cần thiết để có được cùng một chuỗi trong C ++

Tuyên bố vấn đề

Cho một chuỗi, chúng ta cần tìm số lần quay tối thiểu cần thiết để có được chuỗi tương tự

Ví dụ

Nếu chuỗi đầu vào là “bbbbb” thì cần tối thiểu 1 vòng quay

Thuật toán

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

Ví dụ

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

Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau

Đầu ra

Rotation count = 1