定义
一棵树，用边代表字母，这样一条路径就代表了一个字符串。
实现
用一个数组 $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$，就变成了数的二进制表示。