Бор

Бор (trie) — дерево, в котором каждое ребро помечено символом, а каждая строка набора — путь от корня.

Строки с общим префиксом делят общее начало пути. Добавляя abacaba к бору, где уже есть abac, мы идём по существующим рёбрам, пока они есть, и достраиваем только хвост.

Устройство

struct Trie {
    struct Node {
        array<int, ALPHA> next;
        int cnt = 0;                       // сколько раз строка кончается здесь
        int sub = 0;                       // сколько строк проходит через вершину
        Node() { next.fill(-1); }
    };
    vector<Node> t{Node()};                // 0 — корень

    void insert(const string& s) {
        int v = 0;
        t[v].sub++;
        for (char ch : s) {
            int c = ch - 'a';
            if (t[v].next[c] == -1) { t[v].next[c] = t.size(); t.push_back(Node()); }
            v = t[v].next[c];
            t[v].sub++;
        }
        t[v].cnt++;
    }
};

Вершины лежат в одном vector, ссылки — индексы. Это заметно быстрее, чем узлы на указателях: память идёт подряд, а не разбросана по куче.

Сколько это стоит

Вставка строки — $O(|s|)$. Память — $O(\Sigma |s_i| \cdot |\Sigma|)$: на каждую вершину заводится массив из $|\Sigma|$ ссылок, даже если занята одна.

Для латиницы это 26 int на вершину — 104 байта. Миллион суммарных символов даёт около 100 МБ, и это уже за пределом типичного лимита. Варианты, если не влезает:

• map<char, int> вместо массива — память по факту, но логарифм на переход и большая константа;
• сжатый бор (радиксное дерево), где цепочка вершин без ветвлений хранится одним ребром с подстрокой;
• отказаться от бора в пользу хешей или сортировки строк.

Зачем два счётчика

cnt — сколько строк набора кончается в этой вершине. Нужен, потому что вершина на пути не обязана быть концом строки: добавив abac и ab, мы получаем два конца на одном пути.

sub — сколько строк проходит через вершину, то есть сумма cnt по всему поддереву. Он нужен для запросов и, что важнее, для удаления — об этом отдельно.

Оба поддерживаются прямо во время вставки: sub увеличивается у каждой вершины на пути, cnt — только у последней.

Простейшее применение: сортировка строк

Добавим все строки в бор и обойдём его в глубину, перебирая символы по возрастанию. Строки выпишутся в лексикографическом порядке.

string cur;
vector<string> sorted;
void dfs(int v) {
    for (int i = 0; i < t[v].cnt; i++) sorted.push_back(cur);
    for (int c = 0; c < ALPHA; c++)
        if (t[v].next[c] != -1) {
            cur += 'a' + c;
            dfs(t[v].next[c]);
            cur.pop_back();
        }
}

Работает за суммарную длину строк — против $O(k \log k)$ сравнений строк у обычной сортировки, где каждое сравнение само стоит до длины строки.

Проверено: на 20 000 случайных наборов порядок совпал с std::sort.

Обратите внимание на цикл for (int i = 0; i < t[v].cnt; i++) — он выписывает повторяющиеся строки нужное число раз. С обычным if бор превратился бы в set и потерял дубликаты.

Чем бор лучше множества строк

set<string> умеет то же и пишется одной строкой. Бор берут, когда нужно что-то за пределами хранения:

• запросы по префиксам («сколько строк начинается на abc») — это sub одной вершины;
• обход всех строк в лексикографическом порядке за суммарную длину;
• задачи, где по бору потом строится автомат или считается динамика;
• операции над множеством чисел в двоичной записи — бор на алфавите из двух символов решает, например, «максимальный xor с данным числом».