Как реализовать бор (trie) для вставки и поиска строк, и сколько он ест памяти?

Бор — дерево, где путь от корня до узла кодирует префикс. Каждый узел хранит переходы по символам и флаг «здесь кончается слово». Реализация массивом узлов (а не указателями) на CP быстрее и не течёт.

struct Trie {
    struct Node {
        array<int, 26> next;
        bool leaf = false;
        Node() { next.fill(-1); }
    };
    vector<Node> t{1};                      // корень = узел 0
    void insert(const string& s) {
        int v = 0;
        for (char ch : s) {
            int c = ch - 'a';
            if (t[v].next[c] == -1) {
                t[v].next[c] = t.size();
                t.emplace_back();
            }
            v = t[v].next[c];
        }
        t[v].leaf = true;
    }
    bool contains(const string& s) {
        int v = 0;
        for (char ch : s) {
            int c = ch - 'a';
            if (t[v].next[c] == -1) return false;
            v = t[v].next[c];
        }
        return t[v].leaf;
    }
};

Вставка/поиск — O(|s|) на строку, не зависят от числа строк. Память — O(суммарная длина · алфавит) в худшем случае: при алфавите 26 каждый узел — 26 интов. Если алфавит большой (Unicode, 10^5), массив next раздуется — тогда берите unordered_map<int,int> next (медленнее по константе, но память пропорциональна реальным рёбрам).