C++ प्रोग्राम: दी गई स्ट्रिंग के वर्ण हटाकर शब्दकोश में सबसे बड़ा शब्द ज्ञात करना

मान लें हमारे पास एक शब्दकोश है, और एक स्ट्रिंग s है। शब्दकोश में सबसे लंबी स्ट्रिंग ज्ञात करें, जिसे स्ट्रिंग s के कुछ वर्णों को हटाकर बनाया जा सकता है। मान लें s "apbreoigroakml" है, शब्दकोश में {"prog", "ram", "program"} है, तो परिणाम "program" होगा।

इसे हल करने के लिए, हम सभी शब्दकोश शब्दों को पार करेंगे, और प्रत्येक शब्द के लिए, हम जांचेंगे कि क्या यह दिए गए स्ट्रिंग का उपअनुक्रम है और ऐसे सभी शब्दों में सबसे लंबा है। अंत में दिए गए स्ट्रिंग को उपअनुक्रम के रूप में रखने वाला सबसे लंबा शब्द लौटाएं।

उदाहरण

#include <iostream>
#include <vector>
using namespace std;

bool isSubSequence(string s1, string s2) {
    int m = s1.length(), n = s2.length();
    int j = 0;
    for (int i = 0; i < n && j < m; i++)
        if (s1[j] == s2[i])
            j++;
    return (j == m);
}

string getLongestSubstr(vector dict, string s) {
    string result = "";
    int length = 0;
    for (string word : dict) {
        if (length < word.length() && isSubSequence(word, s)) {
            result = word;
            length = word.length();
        }
    }
    return result;
}

int main() {
    vector dict = {"prog", "ram", "program"};
    string str = "apbreoigroakml";
    cout << getLongestSubstr(dict, str) << endl;
}

आउटपुट

program