Home 字典树(Trie)
Post
Cancel

字典树(Trie)

avatar

这棵字典树用边来代表字母, 从根结点到树上某一结点的路径就代表了一个字符串.

有时需要标记插入 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
// C++ Version
struct trie {
  int nex[100000][26], cnt;
  bool exist[100000];  // 该结点结尾的字符串是否存在

  void insert(char *s, int l) {  // 插入字符串
    int p = 0;
    for (int i = 0; i < l; i++) {
      int c = s[i] - 'a';
      if (!nex[p][c]) nex[p][c] = ++cnt;  // 如果没有,就添加结点
      p = nex[p][c];
    }
    exist[p] = 1;
  }

  bool find(char *s, int l) {  // 查找字符串
    int p = 0;
    for (int i = 0; i < l; i++) {
      int c = s[i] - 'a';
      if (!nex[p][c]) return 0;
      p = nex[p][c];
    }
    return exist[p];
  }
};

模板题: 洛谷 P2580 于是他错误的点名开始了

Link

题目描述: 给你 n 个名字串, 然后进行 m 次点名, 每次你需要判断“名字不存在”、“第一次点到这个名字”、“已经点过这个名字”.

注意, vis 一定要有 3 种状态, 即: 是字符串最后一个字符并且已经被访问过, 就是 2; 是字符串最后一个字符并且之前没有被访问过, 就是 1; 其他情况, 就是 0.

不然 hack 数据过不了. 例如存入的字符串是 ad, 要查找的字符串是 a, 然而查找到字符串 a 的最后一个字符 a 时会发现 nex 是有非零值的, 但是字符 a 并不是 ad 的末尾字符, 这就会被误认为是 OK.

Input:

1
2
3
4
1
ad
1
a

Output:

1
WRONG

AC 代码 - 冗杂版 (我自己的):

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
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
using namespace std;
int n,m,cnt;
int nex[500010][26],vis[500010];
int main() {
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        char s[55];
        scanf("%s",s);
        int p=1;
        for(int j=0;j<strlen(s);++j){
            int c=s[j]-'a';
            if(!nex[p][c]) nex[p][c]=++cnt;
            p=nex[p][c];
        }
        vis[p]=1;
    }
    scanf("%d",&m);
    for(int i=1;i<=m;++i){
        char s[55];
        scanf("%s",s);
        int p=1;
        bool wrong=false,repeat=false;
        for(int j=0;j<strlen(s);++j){
            int c=s[j]-'a';
            p=nex[p][c];
            if(!p){
                wrong=true;
                break;
            }
            if(j==strlen(s)-1){
                if(vis[p]==2) repeat=true;
                else if(vis[p]==1) vis[p]=2;
                else wrong=true;
                break;
            }
        }
        if(wrong) printf("WRONG\n");
        else if(repeat) printf("REPEAT\n");
        else printf("OK\n");
    }
    return 0;
}

AC 代码 - 精简版 (别人的):

代码来源

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 <cstdio>

const int N = 500010;

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

int main() {
  scanf("%d", &n);

  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;  // 如果这个节点的子节点中没有这个字符,添加上并将该字符的节点号记录为++tot
      u = ch[u][c];  // 往更深一层搜索
    }
    tag[u] = 1;  // 最后一个字符为节点 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;  // 最后一个字符为节点 u 的名字已经被访问
      puts("OK");
    } else if (tag[u] == 2)  // 已经被访问,重复访问
      puts("REPEAT");
    else
      puts("WRONG");
  }

  return 0;
}

维护异或极值: 洛谷 P4551 最长异或路径

Link

题目描述: 给定一棵 n 个点的带权树, 结点下标从 1 开始到 n. 寻找树中找两个结点, 求最长的异或路径 (异或路径指的是指两个结点之间唯一路径上的所有边权的异或).

权值小于 2 的 31 次方, 因此权值的二进制表示最多只需要 31 位.

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
#include <algorithm>
#include <cstdio>
using namespace std;

const int N = 100010;

int head[N], nxt[N << 1], to[N << 1], weight[N << 1], cnt;
int n, dis[N], ch[N << 5][2], tot = 1, ans;

void insert(int x) {
  for (int i = 30, u = 1; i >= 0; --i) {
    int c = ((x >> i) & 1);  // 二进制一位一位向下取
    if (!ch[u][c]) ch[u][c] = ++tot;
    u = ch[u][c];
  }
}

void get(int x) {
  int res = 0;
  for (int i = 30, u = 1; i >= 0; --i) {
    int c = ((x >> i) & 1);
    if (ch[u][c ^ 1]) {  // 如果能向和当前位不同的子树走,就向那边走
      u = ch[u][c ^ 1];
      res |= (1 << i); // 既然已经找到了可以走的岔路, 就说明当前比特位不一样, 异或之后一定是 1. 这里相当于将 res 二进制的第 i+1 位置为 1.
    } else
      u = ch[u][c];
  }
  ans = max(ans, res);  // 更新答案
}

void add(int u, int v, int w) {  // 建边
  nxt[++cnt] = head[u];
  head[u] = cnt;
  to[cnt] = v;
  weight[cnt] = w;
}

void dfs(int u, int fa) {
  insert(dis[u]);
  get(dis[u]);
  for (int i = head[u]; i; i = nxt[i]) {  // 遍历子节点
    int v = to[i];
    if (v == fa) continue;
    dis[v] = dis[u] ^ weight[i];
    dfs(v, u);
  }
}

int main() {
  scanf("%d", &n);

  for (int i = 1; i < n; ++i) {
    int u, v, w;
    scanf("%d%d%d", &u, &v, &w);
    add(u, v, w);  // 双向边
    add(v, u, w);
  }

  dfs(1, 0);

  printf("%d", ans);

  return 0;
}

维护异或和

参考

This post is licensed under CC BY 4.0 by the author.