এই সমস্যায়, আমাদেরকে একটি স্ট্রিং এবং একটি পূর্ণসংখ্যা M দেওয়া হয়েছে। আমাদের কাজ হল M দৈর্ঘ্যের সমস্ত স্বতন্ত্র বৃত্তাকার স্ট্রিংগুলিকে আভিধানিক ক্রমে (বর্ণানুক্রমিক ক্রম) মুদ্রণ করা।
সমস্যাটি বোঝার জন্য একটি উদাহরণ দেওয়া যাক,
Input: str= “ssssn” M=3 Output: nss sns ssn sss
ব্যাখ্যা − 3 দৈর্ঘ্যের সমস্ত সম্ভাব্য বৃত্তাকার স্ট্রিং হল:sss sss ssn sns nss. আভিধানিক ক্রমে স্বতন্ত্র উপাদান হল ssss ssn sns nsns.
এই সমস্যাটি সমাধান করার জন্য, আমরা স্ট্রিং এর উপাদানগুলির উপর পুনরাবৃত্তি করব এবং 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
