Trie
Eva.Q Lv9
2022-04-23 15:22:28

踹树 ！！

他们今天在打天梯赛！

我做了两道 cf ，然后有点不想做题了，想起来 Co 老师前几天教我的 Trie 树还没有写笔记（我太懒了，总是不写，问题是不写我还会忘，Co 老师就会很生气，为了不被逐出师门，我决定好好学习

Trie

啥是 Trie 树

顾名思义，它应该是一个树……

这个树给我一种很像自动机的感觉

官方回答：Trie 树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。

咋建立的

这个建立的过程十分的自动机…… 由于我实在是口拙，还是举例子说一下吧

比如给了两个串，abc 和 abdc

处理第一个串的时候，从 1 号结点建立一条 a 的出边到 2 号结点，再从 2 号结点建立一条 b 的出边到 3 号结点，再从 3 号结点建立一条 c 的出边到 4 号结点。

处理第二个串的时候，从 1 号结点开始，因为 1 号结点已经有 a 出边，故顺着这条边到 2 号结点，因为 2 号结点有 b 出边，故顺着这条边到 3 号结点，因为 3 号结点没有 d 的出边，故从 3 号结点建立一条 d 的边到 5 号结点，再从 5 号结点建立一条 c 的出边到 6 号结点。

例题

口胡题1

给一堆字符串，若干次询问，每次询问一个串是否是那一堆字符串中任意一个串的前缀。

解：看能否再 Trie 树上找到一条路径来匹配当前串。

口胡题2

给一堆字符串，若干次询问，每次询问一个串是那一堆字符串中多少个串的前缀。

解：每个结点加个计数器。

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

这道题大概就是，一个老师要点名，问是否存在该名字，如果第一次点到这个人输出 OK ，没有这个人输出 WRONG ，如果不是第一次点输出 REPEAT 。

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
#include<bits/stdc++.h>
using namespace std;

inline int rd() {
    bool f = 0;
    int x = 0;
    char c = getchar();
    for (;!isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
    return f ? -x : x;
}

struct node {
    int nxt[26], cnt;
}c[500007];

int nodecnt;
string s;

void insert() {
    int rt = 0, len = s.length();
    for (int i = 0; i < len; ++i) {
        int w = s[i] - 'a';
        if (!c[rt].nxt[w]) c[rt].nxt[w] = ++nodecnt;
        rt = c[rt].nxt[w];
    }
}

int query() {
    int rt = 0, len = s.length();
    for (int i = 0; i < len; ++i) {
        int w = s[i] - 'a';
        if (!c[rt].nxt[w]) return 0;
        rt = c[rt].nxt[w];
    }
    return ++c[rt].cnt;
}

int main() {
    int n = rd();
    for (int i = 1; i <= n; ++i) {
        cin >> s; insert();
    }
    int m = rd();
    for (int i = 1; i <= m; ++i) {
        cin >> s; int ans = query();
        if (ans == 0) puts("WRONG");
        else if (ans == 1) puts("OK");
        else puts("REPEAT");
    }
    return 0;
}
SPOJ 4033 Phone List

这是道洛谷要 waiting 亿万年的题目…… 最后是 Co 老师在 SPOJ 上帮我测的代码

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
#include<bits/stdc++.h>
using namespace std;

inline int rd() {
    bool f = 0;
    int x = 0;
    char c = getchar();
    for (;!isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
    return f ? -x : x;
}

struct node {
    int nxt[26], cnt, fl;
}c[100007];

int nodecnt;
string s;

void insert() {
    int rt = 0, len = s.length();
    for (int i = 0; i < len; ++i) {
        int w = s[i] - '0';
        if (!c[rt].nxt[w]) c[rt].nxt[w] = ++nodecnt;
        rt = c[rt].nxt[w]; ++c[rt].cnt;
    }
    c[rt].fl = 1;
}

inline void work() {
    for (int i = 0; i <= nodecnt; ++i) {
        c[i].cnt = c[i].fl = 0;
        memset(c[i].nxt, 0, sizeof(c[i].nxt));
    }
    nodecnt = 0;
    int n = rd();
    for (int i = 1; i <= n; ++i) {
        cin >> s; insert();
    }
    for (int i = 1; i <= nodecnt; ++i)
        if (c[i].fl && c[i].cnt >= 2) {puts("NO"); return;}
    puts("YES");
}

int main() {
    for (int t = rd(); t; --t) work();
    return 0;
}

Trie 树 Function++

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
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
#include<bits/stdc++.h>
#define ll long long
#define N 1007
#define mod 998244353
using namespace std;

inline int rd() {
    bool f = 0;
    int x = 0;
    char c = getchar();
    for (;!isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

int a[1 << 17], l, r, totnode;

struct node {
    int nxt[2];
}c[2000007];

void build(int x) {
	int rt = 0;
	for (int i = 17; i >= 0; --i) {
		int w = ((x & (1 << i)) > 0);
		if (c[rt].nxt[w] == 0) c[rt].nxt[w] = ++totnode;
        rt = c[rt].nxt[w];
	}
}

int checkmx(int x) {
	int rt = 0, res = 0;
	for (int i = 17; i >= 0; --i) {
		int w = ((x & (1 << i)) > 0);
		if (c[rt].nxt[w ^ 1]) {
			res += (1 << i);
			rt = c[rt].nxt[w ^ 1];
		} else rt = c[rt].nxt[w];
	}
	return res;
}

int checkmn(int x) {
	int rt = 0, res = 0;
	for (int i = 17; i >= 0; --i) {
		int w = ((x & (1 << i)) > 0);
		if (c[rt].nxt[w]) {
			rt = c[rt].nxt[w];
		} else {
			res += (1 << i);
            rt = c[rt].nxt[w ^ 1];
        }
	}
	return res;
}

inline void work() {
    for (int i = 0; i <= totnode; ++i)
        for (int j = 0; j < 2; ++j) c[i].nxt[j] = 0;
    totnode = 0;
    l = rd(); r = rd();
    for (int i = 1; i <= r - l + 1; ++i) build(a[i] = rd());
    for (int i = 1; i <= r - l + 1; ++i) {
        if (checkmx(a[i] ^ l) == r && checkmn(a[i] ^ l) == l) {printf("%d\n", a[i] ^ l); return;}
    }
}

int main() {
    for (int t = rd(); t; --t) work();
    return 0;
}
  • Post title：Trie
  • Post author：Eva.Q
  • Create time：2022-04-23 15:22:28
  • Post link：https://qyy/2022/04/23/Algorithm/Trie/
  • Copyright Notice：All articles in this blog are licensed under BY-NC-SA unless stating additionally.