Trie

trie.cpp

struct Trie {
    const static int MAXCHAR = 26;
    struct Vertex {
        int nxt[MAXCHAR];
        bool leaf = false;
        Vertex() { fill(begin(nxt), end(nxt), -1); }
        int &operator[](int x) { return nxt[x]; }
    };
    Trie() : trie(1) {}
    vector<Vertex> trie;
    Vertex &operator[](int x) { return trie[x]; }
    void add_string(string const &s) {
        int v = 0;
        for (char ch : s) {
            int c = ch - 'a';
            if (trie[v][c] == -1) {
                trie[v][c] = trie.size();
                trie.emplace_back();
            }
            v = trie[v][c];
        }
        trie[v].leaf = true;
    }
};