In Tất Cả Chuỗi Tròn Riêng Biệt Độ Dài M Theo Thứ Tự Từ Điển Trong C++

Trong bài toán này, chúng ta được cho một chuỗi và một số nguyên M. Nhiệm vụ là in tất cả các chuỗi tròn (circular) riêng biệt độ dài M theo thứ tự từ điển (alphabetical order).

Ví dụ để hiểu vấn đề:

Đầu vào: str = "ssssn", M = 3
Đầu ra: nss sns ssn sss

Giải thích – Tất cả chuỗi tròn độ dài 3 có thể: sss, sss, ssn, sns, nss. Các phần tử riêng biệt theo thứ tự từ điển: nss, sns, ssn, sss.

Để giải quyết, ta lặp qua các phần tử của chuỗi và sinh tất cả chuỗi con độ dài M. Lưu chuỗi sinh ra vào set (chỉ lưu phần tử riêng biệt, loại bỏ trùng lặp). Set tự động sắp xếp theo thứ tự từ điển. In tất cả phần tử của set từ đầu.

Độ phức tạp phụ thuộc vào độ dài chuỗi con và chuỗi gốc: O(N*M).

Ví Dụ

Mã minh họa giải pháp:

#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 << "Tất cả chuỗi tròn độ dài " << M << " từ chuỗi '" << str << "' là:\n";
    printCircularString(str, N, M);
    return 0;
}

Đầu Ra

Tất cả chuỗi tròn độ dài 3 từ chuỗi 'ssssn' là: nss sns ssn sss