C++에서 사전순으로 길이가 M인 고유한 모든 원형 문자열을 인쇄합니다.

이 문제에서는 문자열과 정수 M이 제공됩니다. 우리의 임무는 사전순(알파벳 순서)으로 길이가 M인 모든 고유한 원형 문자열을 인쇄하는 것입니다.

문제를 이해하기 위해 예를 들어보겠습니다.

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

설명 - 길이가 3인 가능한 모든 원형 문자열은 다음과 같습니다. sss sss ssn sns nss. 사전순의 고유한 요소는 ssssn sns nss.입니다.

이 문제를 해결하기 위해 문자열의 요소를 반복하고 길이가 M인 가능한 모든 하위 문자열을 생성합니다. 이 생성된 문자열을 고유한 요소만 저장하고 중복을 버리는 집합에 저장합니다. 사전순으로 이러한 요소를 저장합니다. 세트의 모든 요소를 ​​처음부터 인쇄합니다.

이 알고리즘은 부분 문자열의 크기와 문자열의 길이에 따라 달라집니다. 시간 복잡도 =O(N*M) .

예

이 코드는 우리 솔루션의 구현을 보여줍니다 -

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

출력

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