Xoay chuỗi theo thứ tự từ điển nhỏ nhất (Lexicographically minimum string rotation)

Giới thiệu

Giả sử một chuỗi được cho, ta biết chuỗi là một dãy ký tự. Xoay theo thứ tự từ điển (Lexicographical rotation) là xoay chuỗi để chuyển các ký tự theo thứ tự từ điển.

Giải pháp đơn giản: ta đơn giản nối chuỗi cho trước với chính nó, sau đó trong một mảng khác, tất cả các xoay của chuỗi được lưu trữ. Sau đó sắp xếp mảng theo thứ tự tăng dần, giá trị thấp nhất là kết quả cuối cùng.

Đầu vào và Đầu ra

Đầu vào: Chuỗi "BCAAFAABCD"
Đầu ra: Chuỗi xoay: "AABCDBCAAF"

Thuật toán

minStrRotation(str)
Đầu vào: Chuỗi cho trước.
Đầu ra: Xoay chuỗi tối thiểu cần thiết.

Begin
    n := độ dài của str
    định nghĩa strArr để lưu tất cả các xoay
    tempStr := nối str với str lần nữa
    for i := 0 to n, do
        strArr[i] := chuỗi con của tempStr từ (i đến n)
    done
    sắp xếp strArr
    return strArr[0]
End

Ví dụ (C++)

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

string minStrRotation(string str) {
    int n = str.size();
    string strArray[n];  // mảng lưu tất cả các xoay của str
    string tempStr = str + str;  // nối str hai lần
    for (int i = 0; i < n; i++)
        strArray[i] = tempStr.substr(i, n);  // lấy chuỗi con từ chỉ số i đến n
    sort(strArray, strArray+n);
    return strArray[0];  // chỉ số đầu tiên là kết quả
}

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

Kết quả

Enter String: BCAAFAABCD
Rotated String: AABCDBCAAF