字典树（trie）学习笔记

发表于 分类于

定义

一棵树，用边代表字母，这样一条路径就代表了一个字符串。

实现

用一个数组 $trie_{i,j}$ 表示第 $i$ 个节点，下一个字符为 $j$ 的节点。

用 $ex_i$ 表示以 $i$ 为结尾的字符串是否存在。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
inline void insert(int l, string x)
{
    int nx = 0;

    for (int i = 0; i < l; i++) {
        int c = x[i] - 'a' + 1;
        if (!trie[nx][c])
            trie[nx][c] = ++cnt;
        nx = trie[nx][c];
    }
    ex[nx] = 1;
}
inline bool find(int l, string x)
{
    int nx = 0;

    for (int i = 0; i < l; i++) {
        int c = x[i] - 'a' + 1;
        if (!trie[nx][c])
            return false;
        nx = trie[nx][c];
    }
    return ex[nx];
}

也可以把字符变成 $0/1$，就变成了数的二进制表示。