Trie - Course 4

Module 1: Trie

Trie

Module 2: Sparse Table

Sparse table

Module 3: Segment Tree

Segment tree
Maximum subarray sum on a given segment

Module 4: Segment Tree Lazy propagation

Segment Tree with Lazy Propagation

Module 5: More on trees

Euler order of visiting vertices
DP on a tree (Tree DP)

Module 6: Binary jumping

Binary Lifting (Jumps)
Lowest common ancestor

Module 7: Cyclic Games

Games on Cyclic Graphs

Module 8: Divide & Conquer

Divide and conquer

Module 9: SQRT Techniques

SQRT Decomposition
SQRT heuristics
Mo’s Algorithm

Home Courses Resources Problems National Olympiad Contests Leaderboard

...

Home/Courses/Course 4/Module 1: Trie/Trie

Trie

Trie

Introduction

A trie is a data structure for storing a set of strings, representing a rooted tree with characters on the edges.

Each vertex of the tree represents a string - consisting of the sequential запись of all characters on the path from the root to this vertex.

Tree construction

At the beginning, a tree is created from a single vertex $v_{root}$ (the root of the tree). This vertex represents the empty string.

Let $\text{edge}(x, g)$ denote the vertex to which we will go along the edge from vertex $x$ with character .

g

g

Adding a string

Let $S$ be a string of length $m$ that we want to add. And $X = root$ . Then sequentially for each $i = 0 \ldots m-1$ we do the following:

If there is an edge $\text{edge}(X, S_i)$ then we go along this edge. I.e. $X = \text{edge}(X, S_i)$ .
Otherwise we create a new edge $\text{edge}(X, S_i)$ and go along it. I.e. $\text{edge}(X, S_i) = \text{New Node}()$ and .

At the end, vertex $X$ will represent the string $S$ . We can mark this vertex as terminal.

Searching for a string and outputting all added strings

To output all strings, it is enough to traverse the tree and output all strings of terminal vertices.

To find the string $S$ you need to traverse the tree and if at some point an edge does not exist, then this string does not exist. Otherwise we return the found vertex.

Deleting a string

We find the string in the TRIE and remove the terminal vertex mark.

Code

New Node

(

)

X = \text{edge}(X, S_i)

int G;
int edge[N][26];
int terminal[N];

void init() {
    G = 0;
    for (int i = 0; i < N; i++) {
        terminal[i] = 0;
        for (int j = 0; j < 26; j++) {
            edge[i][j] = 0;
        }
    }
}

void add_string(string s) {
    int x = 0;

    for (char c: s) {
        int g = c - 'a';

        if (!edge[x][g]) {
            edge[x][g] = ++G;
        }

        x = edge[x][g];
    }

    terminal[x] += 1;
}

int find_string(string s) {
    int x = 0;

    for (char c: s) {
        int g = c - 'a';

        if (!edge[x][g]) {
            return -1;
        }
        x = edge[x][g];
    }

    return x;
}