引入

当我们需要维护很多字符串，并支持下面这类操作时：

  • 插入一个字符串
  • 查询某个字符串是否出现过
  • 查询某个字符串是不是某些字符串的前缀
  • 统计以某个前缀开头的字符串个数

如果直接用 std::set 或 std::map 当然也能做，但有时候我们更需要一个专门处理字符串前缀的信息结构。

这就是 Trie，也叫字典树。

它本质上是一棵树，每条边表示一个字符，从根到某个节点的一条路径，就对应一个字符串前缀。

基本思想

假设只处理小写字母，那么每个节点最多有 26 个儿子，分别表示字符 'a' 到 'z'。

从根节点出发：

  • 插入字符串时，按字符一个一个往下走
  • 如果某条边不存在，就新建节点
  • 最后在字符串结尾位置打个标记，表示这里是某个字符串的结尾

例如插入：

  • abc
  • abd
  • bcd

那么根节点会先分出 'a' 和 'b' 两条边。

其中 abc 和 abd 会共享前缀 ab，这就是 Trie 的意义：把公共前缀合并起来。

数组实现

竞赛里最常见的写法是数组实现。

1
2
int trie[N][26], tot;
bool ed[N];

含义如下：

  • trie[p][c] 表示节点 p 通过字符 c 转移到哪个节点
  • tot 表示当前一共用了多少个节点
  • ed[p] 表示节点 p 是否是某个字符串的结尾

一般令根节点编号为 0。

插入字符串

1
2
3
4
5
6
7
8
9
void insert(std::string s) {
  int p = 0;
  for (char ch : s) {
    int c = ch - 'a';
    if (!trie[p][c]) trie[p][c] = ++tot;
    p = trie[p][c];
  }
  ed[p] = true;
}

过程很好理解：

  • 从根开始
  • 看当前字符对应的儿子是否存在
  • 不存在就新建
  • 最后走到末尾，标记为字符串结尾

查询字符串是否存在

1
2
3
4
5
6
7
8
9
bool find(std::string s) {
  int p = 0;
  for (char ch : s) {
    int c = ch - 'a';
    if (!trie[p][c]) return false;
    p = trie[p][c];
  }
  return ed[p];
}

注意最后不能只判断路径是否存在，还要判断 ed[p]。

因为如果插入了 abcd，那么查询 abc 时路径确实存在，但 abc 未必是一个完整插入过的字符串。

查询前缀是否存在

如果只是判断某个字符串是不是某些字符串的前缀，那么只需要判断这条路径能不能走完：

1
2
3
4
5
6
7
8
9
bool startsWith(std::string s) {
  int p = 0;
  for (char ch : s) {
    int c = ch - 'a';
    if (!trie[p][c]) return false;
    p = trie[p][c];
  }
  return true;
}

这也是 Trie 相比普通哈希表更擅长的地方：前缀查询很自然。

完整模板

例题：洛谷 P2580 于是他错误的点名开始了。

下面先给一个最基础的 Trie 模板。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <bits/stdc++.h>

const int N = 1e6 + 10;
int trie[N][26], tot;
bool ed[N];

void insert(const std::string &s) {
  int p = 0;
  for (char ch : s) {
    int c = ch - 'a';
    if (!trie[p][c]) trie[p][c] = ++tot;
    p = trie[p][c];
  }
  ed[p] = true;
}

bool find(const std::string &s) {
  int p = 0;
  for (char ch : s) {
    int c = ch - 'a';
    if (!trie[p][c]) return false;
    p = trie[p][c];
  }
  return ed[p];
}

int main() {
  std::cin.tie(0)->sync_with_stdio(0);
  int n;
  std::cin >> n;
  while (n--) {
    std::string s;
    std::cin >> s;
    insert(s);
  }
  int q;
  std::cin >> q;
  while (q--) {
    std::string s;
    std::cin >> s;
    std::cout << (find(s) ? "YES" : "NO") << '\n';
  }
  std::cout.flush();
  return 0;
}

统计出现次数

有时不仅要判断字符串是否出现过，还要统计某个字符串插入了多少次。

那么把 ed 换成计数数组即可：

1
2
3
4
5
6
7
8
9
10
11
int cnt[N];

void insert(std::string s) {
  int p = 0;
  for (char ch : s) {
    int c = ch - 'a';
    if (!trie[p][c]) trie[p][c] = ++tot;
    p = trie[p][c];
  }
  ++cnt[p];
}

查询时返回 cnt[p] 即可。

统计前缀个数

如果要求“有多少个字符串以某个前缀开头”，那么可以在每个节点维护有多少字符串经过这个点。

1
2
3
4
5
6
7
8
9
10
11
int pass[N];

void insert(std::string s) {
  int p = 0;
  for (char ch : s) {
    int c = ch - 'a';
    if (!trie[p][c]) trie[p][c] = ++tot;
    p = trie[p][c];
    ++pass[p];
  }
}

这样查询前缀时，沿着前缀走到最后一个节点，返回 pass[p] 就行。

空间复杂度

Trie 的时间复杂度通常很好分析。

设字符串长度为 m：

  • 插入：O(m)
  • 查询：O(m)

但它的缺点也很明显：比较占空间。

如果节点很多，而每个节点都开 26 个儿子，那么空间会比较大。

所以 Trie 很适合：

  • 字符集较小
  • 字符串数量多
  • 前缀问题明显

如果字符集很大，比如大小写、数字、特殊字符全都要维护，有时就需要改成 map 存边，或者使用其它数据结构。

和哈希的区别

很多人学 Trie 的时候会问：这东西和字符串哈希有什么区别？

简单说：

哈希更擅长

  • 判断字符串是否相等
  • 快速比较子串
  • 做判重

Trie 更擅长

  • 维护一批字符串
  • 查询前缀
  • 统计前缀出现次数
  • 建自动机（比如 AC 自动机）

所以 Trie 的价值不只是“查字符串存不存在”，而是它天然适合处理前缀结构。

扩展：01-Trie

Trie 不一定只能存字符串，也可以存二进制。

比如把一个整数拆成二进制位，从高位到低位插入，就能得到 01-Trie。

它常用于：

  • 求最大异或对
  • 动态维护异或最值
  • 一些与二进制贪心相关的问题

01-Trie 可以看成是普通 Trie 的一个变种，只不过字符集从 26 个字母变成了 {0, 1}。

总结

Trie 本质上是一种维护字符串集合的数据结构，它的核心思想是：

把相同前缀合并到同一条路径上。

它的优点很明确：

  • 插入和查询都是按字符串长度线性进行
  • 前缀查询天然支持
  • 很适合做字符串统计类问题

缺点也很明确：

  • 占空间
  • 写法固定但容易开小数组

如果题目里出现了大量字符串、前缀匹配、字典查询之类的字眼，就可以优先想一想 Trie。