विचार करें कि हमारे पास एक शब्दकोश है, और एक स्ट्रिंग s है। शब्दकोश में सबसे लंबी स्ट्रिंग खोजें, जिसे स्ट्रिंग s के कुछ वर्णों को हटाकर बनाया जा सकता है। मान लीजिए कि s "apbreoigroakml" है, शब्दकोश में {"prog", "ram", "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 <string > 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 <string > dict = {"prog", "ram", "program"};
string str = "apbreoigroakml" ;
cout << getLongestSubstr(dict, str) << endl;
} आउटपुट
program