Số lượng chuỗi con khớp trong C++

Cho chuỗi S và từ điển words. Đếm số từ trong words là chuỗi con (subsequence) của S.

Ví dụ: S = "abcde", words = ["a","bb","acd","ace"] → 3 ("a", "acd", "ace").

Thuật toán giải quyết (Bucket theo ký tự đầu + Duyệt S)

1. Nhóm các từ trong words theo ký tự đầu tiên vào map m[char] = list.
2. Duyệt từng ký tự c trong S:
   • Lấy danh sách temp = m[c], xóa m[c].
   • Với mỗi từ trong temp:
     • Nếu độ dài = 1 → tăng kết quả.
     • Ngược lại → bỏ ký tự đầu, thêm phần còn lại vào m[next_char].
3. Trả về kết quả.

Ví dụ minh họa (C++)

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int numMatchingSubseq(string S, vector<string>& words) {
        unordered_map<char, vector<string>> m;
        for (string &w : words) m[w[0]].push_back(w);
        int ans = 0;
        for (char c : S) {
            auto it = m.find(c);
            if (it == m.end()) continue;
            vector<string> temp = move(it->second);
            m.erase(it);
            for (string &w : temp) {
                if (w.size() == 1) ans++;
                else m[w[1]].push_back(w.substr(1));
            }
        }
        return ans;
    }
};

int main() {
    string s = "abcde";
    vector<string> v = {"a", "bb", "acd", "ace"};
    Solution ob;
    cout << ob.numMatchingSubseq(s, v);
}

Đầu vào

"abcde" ["a","bb","acd","ace"]

Đầu ra

3