Trie

16 Nov 2025

1. Introduction

A Trie, also called a prefix tree, is a data structure designed for strings. It stores strings one character per level. Starting from the root, the characters along a path form a prefix.

For example, when inserting cat and car, the two words share the path c → a and then branch to t and r. This makes a Trie a natural way to store many strings with common prefixes.

For strings containing only lowercase letters, each node usually has 26 child edges: next[u][0] through next[u][25], representing the next character from a through z. The root is commonly assigned index 1.

2. Insertion and Prefix Information

To insert a string, start at the root and read its characters one by one. If the child for the current character does not exist, create a new node, then move to that child. When the string has been read completely, record how many strings end at the final node.

for (char c : s) {
    int id = c - 'a';
    if (!next[u][id]) next[u][id] = ++nodeCount;
    u = next[u][id];
}
endCount[u]++;

endCount[u] is important: it records how many strings end exactly at node u. If the input contains duplicate strings, it should be incremented instead of being stored as only a Boolean value.

Trie insertion and lookup both take time proportional to the string length. If the total length of all strings is L, building the Trie usually takes O(L) time.

3. Example: Luogu P10470: Prefix Statistics

Given N strings S, each query provides a string T and asks how many strings S are prefixes of T.

First, insert all strings S into the Trie. To query T, follow its characters from the root. Whenever a node is reached, add its endCount to the answer, because every string ending there is a prefix of T.

If the child for a character does not exist, later characters cannot match either, so the accumulated value is the answer.

#include <bits/stdc++.h>
using namespace std;

const int N = 1000000 + 10;
int nextNode[N][26];
int endCount[N];
int nodeCount = 1;

void insert(const string& s) {
    int u = 1;
    for (char c : s) {
        int id = c - 'a';
        if (!nextNode[u][id]) nextNode[u][id] = ++nodeCount;
        u = nextNode[u][id];
    }
    endCount[u]++;
}

int query(const string& t) {
    int u = 1;
    int answer = 0;

    for (char c : t) {
        int id = c - 'a';
        if (!nextNode[u][id]) break;
        u = nextNode[u][id];
        answer += endCount[u];
    }
    return answer;
}

int main() {
    int n, m;
    cin >> n >> m;

    while (n--) {
        string s;
        cin >> s;
        insert(s);
    }

    while (m--) {
        string t;
        cin >> t;
        cout << query(t) << '\n';
    }
    return 0;
}

For example, after inserting at, ate, and cat, querying ateam gives 2 because both at and ate are prefixes. Querying cat gives 1.

The key to a Trie is not memorizing a fixed template. Each node represents a prefix, and the problem determines what additional information the node should store: the number of strings ending there, the number passing through it, a subtree size, or a special marker. With the right node information, many string-prefix problems can be solved by following one path through the tree in linear time.

Trie

Related Posts