বিবেচনা করুন আমরা একটি অভিধান আছে, এবং একটি স্ট্রিং এস. অভিধানে দীর্ঘতম স্ট্রিং খুঁজুন, যেটি স্ট্রিং 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 <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
