Số vòng quay tối thiểu để得到 cùng chuỗi trong C++

Đề bài

Cho một chuỗi, cần tìm số vòng quay tối thiểu để được lại chính chuỗi đó.

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. Khởi tạo result = 0
2. Tạo chuỗi tạm bằng chuỗi gốc nối với chính nó.
3. Lấy chuỗi con của chuỗi tạm có kích thước bằng chuỗi gốc bắt đầu từ ký tự thứ 2 (chỉ số 1)
4. Tăng bộ đếm
5. Kiểm tra chuỗi con có bằng chuỗi gốc không. Nếu có thì dừng. Ngược lại quay lại bước 2 và lặp từ chỉ số tiếp theo.

Ví dụ mã C++

#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 << "Số vòng quay = " << getRotationCount(str) << endl;
    return 0;
}

Khi biên dịch và thực thi chương trình trên. Nó tạo ra đầu ra sau

Đầu ra

Số vòng quay = 1