Tìm từ lớn nhất trong từ điển bằng cách xóa một số ký tự của chuỗi đã cho trong C ++

Hãy xem xét chúng ta có một từ điển và một chuỗi s. Tìm chuỗi dài nhất trong từ điển, chuỗi đó có thể được hình thành bằng cách xóa một số ký tự của chuỗi s. Giả sử s là “apbreoigroakml”, Từ điển có {“prog”, “ram”, “program”}, thì kết quả sẽ là “program”.

Để giải quyết vấn đề này, chúng tôi sẽ duyệt qua tất cả các từ trong từ điển và đối với mỗi từ, chúng tôi sẽ kiểm tra xem thứ tự con của chuỗi đã cho và dài nhất trong tất cả các từ như vậy. Cuối cùng trả về từ dài nhất với chuỗi đã cho dưới dạng dãy con.

Ví dụ

#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;
}

Đầu ra

program