洛谷 P8306 【模板】字典树

写模板：
1 确定树的节点指针数量
2 确定起始字符
3 实现插入方法
4 根据题目编写求解方法，或者添加计数元素到节点中

struct Node{
    array<int, 100> next{};
    int cnt = 0;
};

class Trie{
public:
    Trie(char start): start_(start), root_(0){
        trie_.resize(1);
    }

    void insert(const string& s){
        int cur = root_;
        for (const auto& x : s){
            int p = x - start_;
            if (trie_[cur].next[p] == 0){
                trie_.emplace_back();
                trie_[cur].next[p] = trie_.size() - 1;
            }
            cur = trie_[cur].next[p];
            trie_[cur].cnt ++;
        }
    }

    int get(const string& t){
        int cur = root_;
        for (const auto& x : t){
            int p = x - start_;
            if (trie_[cur].next[p] == 0){
                return 0;
            }
            cur = trie_[cur].next[p];
        }
        return trie_[cur].cnt;
    }

private:
    vector<Node> trie_;
    char start_;
    int root_;
};


void solve(){
    int n, q;
    cin >> n >> q;

    Trie trie('0');
    for (int i = 0; i < n; ++i){
        string s;
        cin >> s;
        trie.insert(s);
    }

    while (q --){
        string t;
        cin >> t;
        cout << trie.get(t) << '\n';
    }
}