In tất cả các chuỗi tròn riêng biệt có độ dài M theo thứ tự từ vựng trong C ++

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

Hãy lấy một ví dụ để hiểu vấn đề,

Input: str= “ssssn” M=3
Output: nss sns ssn sss

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

Để giải quyết vấn đề này, chúng tôi sẽ lặp lại các phần tử của chuỗi và tạo tất cả các chuỗi con có thể có độ dài M. Chúng tôi sẽ lưu trữ chuỗi được tạo này trong một tập hợp chỉ lưu trữ các phần tử riêng biệt và loại bỏ các bản sao. Nó sẽ lưu trữ các yếu tố này theo thứ tự từ vựng. In tất cả các phần tử của tập hợp ngay từ đầu.

Thuật toán này sẽ phụ thuộc vào cả kích thước của chuỗi con và độ dài của chuỗi. Độ phức tạp về thời gian = O (N * M) .

Ví dụ

Mã này cho thấy việc triển khai giải pháp của chúng tôi -

#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;
}

Đầu ra

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