Trie

A trie (prefix tree) stores a set of words so that words with the same beginning share one path. It answers "is this word here?" and "how many words start with these letters?" in time proportional to the length of the word. If you only need to find whole words, a set of strings (or a map to count copies) is simpler.

Think of autocompletion: there is a list of words, you type "ca", and the program suggests car, card, care and cat. Checking the words one by one is slow when the list is long; a trie goes straight to the words that start with "ca".

How it works

A trie is a rooted tree. Each edge carries a letter, and edges from one node carry different letters. Each node stands for the letters on the path from the root to it. These letters are a prefix (the first few letters) of some inserted word. The root stands for the empty prefix. The words "car", "card" and "care" all go through the node for "car".

Fig. 1. The trie of car, card, care, cat, dog and do. A node stands for the letters on the path to it; green nodes end a word.

A node has an end mark when an inserted word ends there; the figures draw it green. The node for "car" is green, and "card" and "care" go on below it. The node for "ca" has no mark, because "ca" was never inserted.

Each operation walks from the root along the word's letters:

1. insert: where the edge for the next letter is missing, create a node. Put an end mark on the word's end node.

2. search: if an edge is missing, the word is not there. Otherwise the answer is whether the word's end node has an end mark.

3. count prefix: every node keeps the number of inserted words that start with its prefix. Insert adds 1 to each node on its path, so the answer is the number in the prefix's node, or 0 if an edge is missing.

Let's insert six words and ask four questions.

The trie starts with the root alone. The number in a node counts the inserted words that start with its letters; a green node ends a word.

insert car: the walk creates the nodes c, ca, car and adds 1 on its path (c 1, ca 1, car 1); car turns green.

insert card: c, ca, car already exist; the walk creates card and adds 1 on its path (c 2, ca 2, car 2, card 1); card turns green.

insert care: c, ca, car already exist; the walk creates care and adds 1 on its path (c 3, ca 3, car 3, care 1); care turns green.

insert cat: c, ca already exist; the walk creates cat and adds 1 on its path (c 4, ca 4, cat 1); cat turns green.

insert dog: the walk creates the nodes d, do, dog and adds 1 on its path (d 1, do 1, dog 1); dog turns green.

insert do: every node already exists, so no node is created; the walk adds 1 on its path (d 2, do 2) and do turns green.

search ca: the walk stops at ca, which is not green, because ca was never inserted, so the answer is NO.

search cart: the walk reaches car, which has no edge for the letter t, so the answer is NO.

search do: the walk stops at do, which is green, so the answer is YES.

count car: the walk stops at car and reads its number, so the answer is 3; nothing below car is visited.

1/11

Fig. 2. Step through with the buttons or the arrow keys. The number in a node counts the inserted words that start with its letters.

Inserting "do" created no node, only a mark. The two NOs have different reasons: "cart" hit a missing edge, "ca" a node without a mark. The count for "car" was read from its node, with no search below it.

Each operation makes one step per letter, so it takes $O(L)$, however many words are stored. Each letter creates at most one node, so there are at most (total letters + 1) nodes; the six words above have 19 letters but 10 nodes.

Implementation

The standard library has no trie, so we build one on arrays. Nodes are numbered in the order they are created, the root first.

Let's keep the edges in an array child, where child[v][c] is the child of v along letter c = ch - 'a', or 0 if none. For digits, use ch - '0' and 10 columns. 0 can mean "no child" because node 0 is the root, and no edge leads to the root; global arrays start filled with zeros. Each node also keeps two counters. pass[v] counts the words whose path goes through v: the number drawn in the node in Fig. 2. ending[v] counts the words that end at v, so the end mark is ending[v] > 0; a word inserted twice is kept twice. cnt is the number of nodes so far.

Fig. 3. The trie of Fig. 1 as arrays. Row v holds child[v][c] for the letters that occur; a blank cell means no child.

walk(s) follows the letters of s from the root and returns its end node, or -1 if an edge is missing.

The program reads $q$, then $q$ lines insert w, search w or count p (lowercase words, at most 10^6 letters in total), and prints YES or NO for each search and the count for each count. The run in Fig. 2 has this input:

10
insert car
insert card
insert care
insert cat
insert dog
insert do
search ca
search cart
search do
count car

#include <iostream>
#include <string>
using namespace std;

const int MAXN = 1000001;            // total letters in all words + 1
int child[MAXN][26], pass[MAXN], ending[MAXN];
int cnt = 1;                         // node 0 is the root

// insert
void insert(const string& s) {
    int v = 0;
    for (char ch : s) {
        int c = ch - 'a';            // 'C' - 'a' is -30: for digits use ch - '0' and 10 columns
        if (child[v][c] == 0)        // missing edge: create a node
            child[v][c] = cnt++;
        v = child[v][c];
        pass[v]++;
    }
    ending[v]++;                     // mark the end
}

// the walk
int walk(const string& s) {
    int v = 0;
    for (char ch : s) {
        int c = ch - 'a';
        if (child[v][c] == 0) return -1;
        v = child[v][c];
    }
    return v;
}

// search
bool search(const string& s) {
    int v = walk(s);
    return v != -1 && ending[v] > 0;
}

// count prefix
int countPrefix(const string& p) {
    int v = walk(p);
    return v == -1 ? 0 : pass[v];
}

int main() {
    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        string cmd, w;
        cin >> cmd >> w;
        if (cmd == "insert") insert(w);
        else if (cmd == "search") cout << (search(w) ? "YES" : "NO") << '\n';
        else cout << countPrefix(w) << '\n';
    }
}

To remove a word that is in the trie, walk it again, subtracting 1 from pass on the path and from ending at its end node; the nodes stay. When the input has several test cases, clear the rows in use before each new one, or after insert car in test 1, search car in test 2 says YES:

for (int v = 0; v < cnt; v++) {
    memset(child[v], 0, sizeof child[v]);   // needs #include <cstring>
    pass[v] = ending[v] = 0;
}
cnt = 1;

Examples of use

• Autocompletion: the words with the typed prefix are the end marks below its node.

• A phone list where no number is a prefix of another: after inserting all numbers, check that pass[v] is 1 at every number's end node v.

• Distinct substrings of a string of length $n$: insert every suffix; each node but the root is one substring. The trie has up to n(n + 1)/2 nodes besides the root, so for long strings use a suffix array.

• Numbers as strings of bits, highest bit first (a binary trie): the longest stored bit string that is a prefix of a query number, the largest XOR of two numbers.

• Words in sorted order: a depth-first search that visits children in letter order.

Similar structures

A hash map from the hash of every prefix to the number of words with that prefix also answers count prefix, but two different prefixes can, rarely, share a hash. A trie has no collisions.

The Aho–Corasick algorithm adds links to a trie of patterns to find them all in one pass over a text.

Practice