<p>Given a string <code>s</code> and an array of strings <code>words</code>, return <em>the number of</em> <code>words[i]</code> <em>that is a subsequence of</em> <code>s</code>.</p>

<p>A <strong>subsequence</strong> of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.</p>

<ul>
	<li>For example, <code>&quot;ace&quot;</code> is a subsequence of <code>&quot;abcde&quot;</code>.</li>
</ul>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;abcde&quot;, words = [&quot;a&quot;,&quot;bb&quot;,&quot;acd&quot;,&quot;ace&quot;]
<strong>Output:</strong> 3
<strong>Explanation:</strong> There are three strings in words that are a subsequence of s: &quot;a&quot;, &quot;acd&quot;, &quot;ace&quot;.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;dsahjpjauf&quot;, words = [&quot;ahjpjau&quot;,&quot;ja&quot;,&quot;ahbwzgqnuk&quot;,&quot;tnmlanowax&quot;]
<strong>Output:</strong> 2
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 5 * 10<sup>4</sup></code></li>
	<li><code>1 &lt;= words.length &lt;= 5000</code></li>
	<li><code>1 &lt;= words[i].length &lt;= 50</code></li>
	<li><code>s</code> and <code>words[i]</code> consist of only lowercase English letters.</li>
</ul>

class TrieNode {   
public:
    TrieNode *nxt[26];
    int cnt_terminals;
    TrieNode() {
        cnt_terminals = 0;
        for (auto &v : nxt) v = nullptr;
    }
};

class Trie {
public:
    TrieNode *root;

    Trie() {
        root=new TrieNode();
    }
    
    void insert(string word) {
        TrieNode* v = root;
        for (char ch: word) {
            if (v->nxt[ch - 'a'] == NULL) {
                TrieNode* node = new TrieNode();
                v->nxt[ch - 'a'] = node;
            }
            v = v->nxt[ch - 'a'];
        }
        v->cnt_terminals++;
    }
};

class Solution {
public:

    int dfs(TrieNode *v, string &s, vector <vector <int>> &where, int idx) {
        int res = 0;
        for (int i = 0; i < 26; i++) {
            if (v->nxt[i]) {
                int l = 0;
                int r = where[i].size() - 1;
                int newIdx = -1;
                while (l <= r) {
                    int mid = (l + r) >> 1;
                    if (where[i][mid] > idx) {
                        newIdx = mid;
                        r = mid - 1;
                    } else {
                        l = mid + 1;
                    }
                }
                if (newIdx == -1) continue;
                res += dfs(v->nxt[i], s, where, where[i][newIdx]);
            }
        }
        return res + v->cnt_terminals;
    }

    int numMatchingSubseq(string s, vector<string>& words) {
        Trie trie;
        for (string w: words) {
            trie.insert(w);
        }
        vector <vector <int>> where(26);
        for (int i = 0; i < s.size(); ++i) {
            where[s[i] - 'a'].push_back(i);
        }
        int ans = dfs(trie.root, s, where, -1);
        return ans;
    }
};
280028