Chương trình C++ tìm từ dài nhất trong từ điển bằng cách xóa ký tự từ chuỗi cho trước

Cho từ điển và chuỗi s. Tìm chuỗi dài nhất trong từ điển có thể tạo được bằng cách xóa một số ký tự của s. Ví dụ s="apbreoigroakml", từ điển {"prog", "ram", "program"} → kết quả "program".

Giải pháp: duyệt tất cả từ trong từ điển, kiểm tra từ nào là dãy con của s và dài nhất.

Ví dụ mã nguồn

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

Kết quả đầu ra

program