C++ में लेक्सिकोग्राफिकली X-वां सबसे छोटा सबस्ट्रिंग ढूंढने की क्वेरी

इस समस्या में, हमें एक स्ट्रिंग str और Q क्वेरी दी गई हैं। प्रत्येक क्वेरी में एक संख्या X है। हमारा कार्य C++ में लेक्सिकोग्राफिकली 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

4था सब-स्ट्रिंग - n

7वां सब-स्ट्रिंग - oi

2रा सब-स्ट्रिंग - in

13वां सब-स्ट्रिंग - poin

समाधान दृष्टिकोण

एक सरल समाधान स्ट्रिंग के सभी संभावित सबस्ट्रिंग उत्पन्न करना, उन्हें एक डेटा संरचना में स्टोर करना, और फिर उन्हें लेक्सिकोग्राफिकल क्रम में यानी वर्णमाला क्रम में सॉर्ट करना होगा। फिर क्वेरी में X के लिए, हमें संरचना से संबंधित सबएरे प्रिंट करना होगा।

सबस्ट्रिंग को स्टोर करने के लिए, हम वेक्टर का उपयोग करेंगे।

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