Trie学习笔记

简述

前言

Trie是一种有用的树形数据结构，她可以解决很多字符串问题。

定义

Trie，即字典树，像字典一样的树

字典树的大致效果如下图：

可以发现，从根节点到树上任意节点的路径就代表一个字符串。如 表示的就是字符串 abc 。

我们定义 表示节点 的 字符边指向的下一个节点，

  • 注意到所有边全是有向边，从根方向指向叶子方向。

实现

封装类（摘自 OI Wiki）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
struct trie {
  int nex[100000][26], cnt;
  bool exist[100000];  // 该结点结尾的字符串是否存在

  void insert(char *s, int len) {  // 插入字符串
    int p = 0; // Trie的根节点(这里为0)
    for (int i = 0; i < len; i++) {
      int c = s[i] - 'a';
      if (!nex[p][c]) nex[p][c] = ++cnt;  // 如果没有，就添加结点
      p = nex[p][c];
    }
    exist[p] = true;
  }

  bool find(char *s, int len) {  // 查找字符串
    int p = 0; // Trie的根节点(这里为0)
    for (int i = 0; i < len; i++) {
      int c = s[i] - 'a';
      if (!nex[p][c]) return 0;
      p = nex[p][c];
    }
    return exist[p];
  }
};

例题

模板1

Luogu P2580 于是他错误的点名开始了

这道题有很多种写法，map，暴力等等。要是用Trie写只会显得很装

写法很简单，每次find找到了就是OK或REPEAT，否则是WRONG

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
#include <cstdio>
using namespace std;
constexpr int N = 500010;

char s[N];
int n, m, ch[N][26], tag[N], tot = 1;

int main() {
  scanf("%d", &n);
  //Trie的insert模板
  for (int i = 1; i <= n; ++i) {
    scanf("%s", s + 1);
    int u = 1;
    for (int j = 1; s[j]; ++j) {
      int c = s[j] - 'a';
      if (!ch[u][c]) ch[u][c] = ++tot;
      u = ch[u][c];
    }
    tag[u] = 1;
  }
  scanf("%d", &m);
  while (m--) {
    scanf("%s", s + 1);
    int u = 1;
    for (int j = 1; s[j]; ++j) {
      int c = s[j] - 'a';
      u = ch[u][c];
      if (!u) break;
    }
    if (tag[u] == 1) {
      tag[u] = 2;
      puts("OK");
    } else if (tag[u] == 2)
      puts("REPEAT");
    else
      puts("WRONG");
  }
  return 0;
}

模板2

Luogu P1481 魔族密码

把所有的词插进Trie，对于每个节点，统计从根节点到该节点路上所有能组成一个单词的标记数量。

  • 注意到我们可以在insert操作时直接统计，故可以小优化一下
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
#include <bits/stdc++.h>
using namespace std;
struct trie {
  int nex[100000][26], cnt;
  int exist[100000];  // 该结点结尾的字符串是否存在

  void insert(char *s, int len) {  // 插入字符串
    int p = 0; // Trie的根节点(这里为0)
    int xxx = 0;
    for (int i = 0; i < len; i++) {
      int c = s[i] - 'a';
      if (!nex[p][c]) nex[p][c] = ++cnt;  // 如果没有，
      if (exist[p]) xxx++;
      p = nex[p][c];
    }
    exist[p] = 1 + xxx;
  }

  bool find(char *s, int len) {  // 查找字符串
    int p = 0; // Trie的根节点(这里为0)
    for (int i = 0; i < len; i++) {
      int c = s[i] - 'a';
      if (!nex[p][c]) return 0;
      p = nex[p][c];
    }
    return exist[p];
  }
};
int n;
char ch[205];
trie pwd;
int main() {
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> ch;
        pwd.insert(ch, strlen(ch));
    }
    int ans = 0;
    for(int i = 0; i < 100000; i++) {
        ans = max(ans, pwd.exist[i]);
    }
    cout << ans << endl;
    return 0;
}

进阶1

Luogu P2536 病毒检测

因为DNA模板片段可变性很强，我们将所有DNA片段插入Trie，在树上跑DFS模拟病毒匹配过程（令 表示模板的某个位置上的值）：

  • 若 ，直接向下递归

  • 若 ，对四个分支都向下递归

  • 若 *，这种情况需要分类讨论 * 代表的是否是空集，若是空集，原地 ++，若不是空集，其实就是递归地找 * 这个串

最后累计即可

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1007;
bitset<1007> vis[500007];
//记忆化需要的bitset，为了省空间

struct Trie {
     int ch[500007][5], sz = 0, val[500007];
     //val指以这个位置为结尾的单词数量
     void clear() {
          memset(ch, 0, sizeof(ch));
          sz = 0;
     }
     int idx(char c) { //字符映射
          if (c == 'A') {
               return 1;
          }
          if (c == 'G') {
               return 2;
          }
          if (c == 'T') {
               return 3;
          }
          if (c == 'C') {
               return 4;
          }
          if (c == '?') {
               return 5;
          }
          if (c == '*') {
               return 6;
          }
     }
     void insert(char s[]) {
          int u = 0, len = strlen(s + 1);
          for (int i = 1; i <= len; i++) {
               int x = idx(s[i]);
               if (ch[u][x] == 0) {
                    ch[u][x] = ++sz;
               }
               u = ch[u][x];
          }
          val[u]++;
     }
} Tree;

char vir[1007];//病毒串
int N, L;//分别为RNA串的数量，病毒串的长度
int ans = 0;//可以和病毒串匹配的RNA串数量
void dfs(int stp, int now) { //模式串的第stp位，在trie树上的位置为now
     if (stp == L + 1) {
          ans += Tree.val[now];//更新答案
          Tree.val[now] = 0;//修改val值，避免多加
          return;
     }
     if (vis[now][stp]) {
          return;
     }
     int x = Tree.idx(vir[stp]);
     vis[now][stp] = 1;
     if (x >= 1 && x <= 4) { //若stp位置上是字母
          if (Tree.ch[now][x])
               dfs(stp + 1, Tree.ch[now][x]);
     }
     if (x == 5) { //若是'?'
          for (int i = 1; i <= 4; i++) {
          //向四个方向都可以走
               if (Tree.ch[now][i])
                    dfs(stp + 1, Tree.ch[now][i]);
          }
     }
     if (x == 6) { //若是*
          dfs(stp + 1, now); //第一种情况：空串
          for (int i = 1; i <= 4; i++) { //第二种情况：'*'='?'+'*'
               if (Tree.ch[now][i]) {
                    dfs(stp + 1, Tree.ch[now][i]); //处理'?'
                    dfs(stp, Tree.ch[now][i]); //处理'*'
               }
          }
     }
}
int main() {
     cin >> vir + 1;
     L = strlen(vir + 1);
     cin >> N;
     Tree.clear();
     for (int i = 1; i <= N; i++) {
          char RNA[1007];
          cin >> RNA + 1;
          Tree.insert(RNA);
     }
     dfs(1, 0);
     cout << N - ans << endl;//ans是匹配上的RNA串数
     //题目要求的是匹配不上的串数，故为 N-ans
     return 0;
}

拓展

AC自动机

AC自动机是 以 Trie 的结构为基础，结合 KMP 的思想 建立的自动机，用于解决多模式匹配等任务，她本质上是 Trie 上的自动机

由于AC自动机还需要KMP这个前置芝士，这里不予解释

维护异或极值/异或和

异或极值

将数的二进制表示看做一个字符串，就可以建出字符集为 的 Trie 树

在查询时从 Trie 的根开始，如果能向起始状态的当前位不同的子树走，就向那边走，否则没有选择

异或和

UKE