พิมพ์สตริงวนรอบ (Circular Strings) ความยาว M เรียงเล็กซิโคกราฟิกใน C++

ภาพรวมปัญหา

ได้รับสตริงและจำนวน M ต้องพิมพ์สตริงวนรอบความยาว M ที่ไม่ซ้ำกัน เรียงตามลำดับเล็กซิโคกราฟิก (พจนานุกรม)

ตัวอย่าง

Input: str = "ssssn", M = 3
Output: nss sns ssn sss

คำอธิบาย: สตริงวนรอบความยาว 3 ทั้งหมด: sss, sss, ssn, sns, nss → ตัวที่ไม่ซ้ำเรียงแล้ว: nss, sns, ssn, sss

วิธีแก้ปัญหา

1. ต่อสตริงกับตัวเอง (s + s) เพื่อจัดการวนรอบ
2. ดึง substring ความยาว M เริ่มจากตำแหน่ง 0 ถึง n-1
3. เก็บใน set<string> → กรองซ้ำและเรียงอัตโนมัติ
4. พิมพ์ทุกค่าใน set

Time Complexity: O(N×M)

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

#include <bits/stdc++.h>
using namespace std;

void printCircularString(string s, int l, int m) {
    set<string> circularString;
    s = s + s;
    for (int i = 0; i < l; i++) {
        circularString.insert(s.substr(i, m));
    }
    while (!circularString.empty()) {
        cout << *circularString.begin() << "\t";
        circularString.erase(circularString.begin());
    }
}

int main() {
    string str = "ssssn";
    int N = str.length();
    int M = 3;
    cout << "All circular strings of length " << M << " from the string '" << str << "' are:\n";
    printCircularString(str, N, M);
    return 0;
}

ผลลัพธ์ (Output)

All circular strings of length 3 from the string 'ssssn' are:
nss sns ssn sss