[C++] Trie Based Solution
\n/* \n    Time: O(n*p*logm) | m=s.length | n=words.length | p=words[i].length\n    Space: O(n*p)\n    Tag: Trie, String, DFS, Hashing\n    Difficulty: H\n*/\n\
```\n/* \n    Time: O(n*p*logm) | m=s.length | n=words.length | p=words[i].length\n    Space: O(n*p)\n    Tag: Trie, String, DFS, Hashing\n    Difficulty: H\n*/\n\nclass Node {\npublic:\n    int isTerminal;\n    vector<Node *> children;\n    Node() {\n        children.resize(26, NULL);\n        isTerminal = 0;\n    }\n};\n\nclass Trie {\n\npublic:\n    Trie() {\n        root = new Node();\n    }\n\n    Node *root;\n    void insert(string s) {\n        Node *cur = root;\n        for (char ch : s) {\n            if (!cur->children[ch - \'a\']) cur->children[ch - \'a\'] = new Node();\n            cur = cur->children[ch - \'a\'];\n        }\n        (cur->isTerminal)++;\n    }\n\n    int dfs(Node *root, string &s, int idx, vector<int>pos[]) {\n        int res = 0;\n        for (int i = 0; i < 26; i++) {\n            if (root->children[i]) {\n                int newIdx = upper_bound(pos[i].begin(), pos[i].end(), idx) - pos[i].begin();\n                if (newIdx == pos[i].size()) continue;\n                res += dfs(root->children[i], s, pos[i][newIdx], pos);\n            }\n        }\n        return res + root->isTerminal;\n    }\n};\n\nclass Solution {\npublic:\n    int numMatchingSubseq(string s, vector<string> &words) {\n        Trie *t = new Trie;\n        for (string str : words) {\n            t->insert(str);\n        }\n        vector<int> pos[26];\n        for (int i = 0; i < s.length(); i++) {\n            pos[s[i] - \'a\'].push_back(i);\n        }\n        return t->dfs(t->root, s, -1, pos);\n    }\n};\n```
['String', 'Depth-First Search', 'Trie', 'C', 'C++']