এই সমস্যায়, আমাদের একটি স্ট্রিং str এবং Q কোয়েরি দেওয়া আছে। প্রতিটি কোয়েরিতে একটি সংখ্যা X থাকে। আমাদের কাজ হল X-তম লেক্সিকোগ্রাফিক্যালি (শব্দকোষ ক্রমে) ছোট সাবস্ট্রিং বের করার কোয়েরি সমাধান করার প্রোগ্রাম তৈরি করা।
সমস্যা বর্ণনা
আমাদের X-তম লেক্সিকোগ্রাফিক্যালি ছোট সাবস্ট্রিং বের করতে হবে অর্থাৎ অ্যালফাবেটিক্যালি সর্ট করে X-তম সাবস্ট্রিং খুঁজে বের করতে হবে।
উদাহরণ দিয়ে বোঝা যাক
ইনপুট: str = "point"
Q = 4 query = {4, 7, 2, 13}
আউটপুট: n, oi, in, poin
ব্যাখ্যা
str-এর সকল সাবস্ট্রিং লেক্সিকোগ্রাফিক্যালি সর্ট করা অবস্থায় -
i, in, int, n, nt, o, oi, oin, oint, p, po, poi, poin, point, t
৪র্থ সাবস্ট্রিং - n
৭ম সাবস্ট্রিং - oi
২য় সাবস্ট্রিং - in
১৩তম সাবস্ট্রিং - poin
সমাধান পদ্ধতি
একটি সহজ সমাধান হল স্ট্রিং-এর সকল সম্ভাব্য সাবস্ট্রিং জেনারেট করা, সেগুলো একটি ডেটা স্ট্রাকচারে সংরক্ষণ করা, এবং তারপর সেগুলো লেক্সিকোগ্রাফিক্যালি অর্ডারে সর্ট করা। তারপর কোয়েরির X অনুযায়ী সংশ্লিষ্ট সাবঅ্যারে প্রিন্ট করা।
সাবস্ট্রিং সংরক্ষণের জন্য ভেক্টর (vector) ব্যবহার করা হবে।
C++ প্রোগ্রাম উদাহরণ
#include <bits/stdc++.h>
using namespace std;
vector<string> substrings;
void find_SortSubstrings(string s) {
int len = s.size();
for (int i = 0; i < len; i++) {
string dup = "";
for (int j = i; j < len; j++) {
dup += s[j];
substrings.push_back(dup);
}
}
sort(substrings.begin(), substrings.end());
}
int main(){
string str = "point";
find_SortSubstrings(str);
int Q = 4;
int query[] = { 4, 9, 5, 15 };
for (int i = 0; i < Q; i++)
cout<<"Query "<<(i+1)<<" : The "<<query[i]<<"th smallest sub-string lexicographically is "<<substrings[query[i] - 1] << endl;
return 0;
}
আউটপুট
Query 1 : The 4th smallest sub-string lexicographically is n Query 2 : The 9th smallest sub-string lexicographically is oint Query 3 : The 5th smallest sub-string lexicographically is nt Query 4 : The 15th smallest sub-string lexicographically is t
