การหมุนสตริงแบบ Lexicographically Minimum (Minimum String Rotation)

บทนำ

พิจารณาสตริงที่กำหนด เรารู้ว่าสตริงคือลำดับของตัวอักษร การหมุนแบบ Lexicographical (Lexicographical Rotation) คือการหมุนสตริง เพื่อให้ตัวอักษรเรียงตามลำดับ Lexicographical

วิธีแก้ง่ายๆ: เราเพียงแค่ต่อสตริงที่กำหนดกับตัวมันเอง (Concatenate) แล้วในอาเรย์อีกอันหนึ่ง เก็บการหมุนของสตริงทั้งหมด หลังจากนั้น เรียงอาเรย์ใน ascending order ค่าต่ำสุดคือผลลัพธ์สุดท้าย

อินพุตและเอาต์พุต

Input: สตริง "BCAAFAABCD"
Output: Rotated String: "AABCDBCAAF"

อัลกอริทึม

minStrRotation(str)
Input: สตริงที่กำหนด
Output: Minimum string rotation ที่จำเป็น

Begin
    n := ความยาวของ str
    กำหนด strArr เพื่อเก็บการหมุนทั้งหมด
    tempStr := concatenate str กับ str อีกครั้ง
    for i := 0 to n, do
        strArr[i] := substring ของ tempStr จาก (i ถึง n)
    done
    เรียง strArr
    return strArr[0]
End

ตัวอย่างโค้ด (C++)

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

string minStrRotation(string str) {
    int n = str.size();
    string strArray[n];  // อาเรย์เก็บการหมุนทั้งหมดของ str
    string tempStr = str + str;  // concatenate str สองครั้ง
    for (int i = 0; i < n; i++)
        strArray[i] = tempStr.substr(i, n);  // ดึง substring จาก index i ถึง n
    sort(strArray, strArray+n);
    return strArray[0];  // index แรกคือผลลัพธ์
}

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

ผลลัพธ์

Enter String: BCAAFAABCD
Rotated String: AABCDBCAAF