# 792. Number of Matching Subsequences

Given string `S` and a dictionary of words `words`, find the number of `words[i]` that is a subsequence of `S`.

```
Example :
Input: 
S = "abcde"
words = ["a", "bb", "acd", "ace"]
Output: 3
Explanation: There are three words in words that are a subsequence of S: "a", "acd", "ace".
```

**Note:**

* All words in `words` and `S` will only consists of lowercase letters.
* The length of `S` will be in the range of `[1, 50000]`.
* The length of `words` will be in the range of `[1, 5000]`.
* The length of `words[i]` will be in the range of `[1, 50]`.

```cpp
// Optimized Brute Force with Hashset
int numMatchingSubseq(string S, vector<string>& words) { // time: O(words_len * S_len); space: O(words_len)
    int res = 0, n = S.length();
    unordered_set<string> valid, invalid;
    for (string word : words) {
        if (valid.count(word) || invalid.count(word)) {
            if (valid.count(word)) ++res;
            continue;
        }
        // Use two pointers to check
        int i = 0, j = 0, m = word.length();
        while (i < n && j < m) {
            if (word[j] == S[i]) ++j;
            ++i;
        }
        if (j == m) {
            ++res;
            valid.insert(word);
        } else invalid.insert(word);
    }
    return res;
}
```

```cpp
// Binary Search
int numMatchingSubseq(string S, vector<string>& words) { // time: O(words_len * average str_len * log(S_len)); space: O(S_len)
    // Build a lookup index table
    vector<vector<int> > idx(26);
    for (int i = 0; i < S.length(); ++i) idx[S[i] - 'a'].push_back(i);
    int res = 0;
    for (const string& word : words) {
        int prev = -1;
        bool found = true;
        for (char c : word) {
            auto it = upper_bound(idx[c - 'a'].begin(), idx[c - 'a'].end(), prev);
            if (it == idx[c - 'a'].end()) {
                found = false;
                break;
            } else prev = *it;
        }
        if (found) ++res;
    }
    return res;
}
```

```cpp
bool isSubsequence(const string& S, const string& word) {
    int idx = -1;
    for (char ch : word) {
        idx = S.find(ch, idx + 1);
        if (idx == -1) return false;
    }
    return true;
}
int numMatchingSubseq(string S, vector<string>& words) {
    int res = 0;
    for (const string& word : words) {
        if (isSubsequence(S, word)) ++res;
    }
    return res;
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/string/792.-number-of-matching-subsequences.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.