【算法学习】Trie算法

本文最后更新于:2022年1月9日晚上9点17分

【Trie树】模板题

题目地址:835. Trie字符串统计 - AcWing题库

Trie字符串统计

维护一个字符串集合,支持两种操作:

  1. I x 向集合中插入一个字符串 xx;
  2. Q x 询问一个字符串在集合中出现了多少次。

共有 NN 个操作,输入的字符串总长度不超过 10^5,字符串仅包含小写英文字母。

输入格式

第一行包含整数 NN,表示操作数。

接下来 NN 行,每行包含一个操作指令,指令为 I xQ x 中的一种。

输出格式

对于每个询问指令 Q x,都要输出一个整数作为结果,表示 xx 在集合中出现的次数。

每个结果占一行。

数据范围

1≤N≤2∗10 ^4

输入样例:

1
2
3
4
5
6
5
I abc
Q abc
Q ab
I ab
Q ab

输出样例:

1
2
3
1
0
1

【Trie数】算法设计

如下图:

image-20220109191136370

【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
#include <iostream>

using namespace std;

const int N = 100010;

char str[N];
int son[N][26], cnt[N], idx = 0;

void insert(char s[]){
int p = 0;
for ( int i = 0; s[i] ; i ++){
int u = s[i] - 'a';
if ( !son[p][u]) son[p][u] = ++idx;
p = son[p][u];
}
cnt[p] ++;
}

int query(char s[]){
int p = 0;
for ( int i = 0; s[i] ; i ++){
int u = s[i] - 'a';
if ( !son[p][u]) return 0;
p = son[p][u];
}
return cnt[p];
}

int main(){
int n;
cin >> n;
char op[2];
while ( n --){
scanf("%s%s",op, str);
if ( op[0] == 'I') insert(str);
else if ( op[0] == 'Q') printf("%d\n", query(str));
}

return 0;
}

【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
#include <iostream>

using namespace std;

const int N = 100010;

char str[N];
int son[N][26], cnt[N], idx = 0;

void insert(char s[]){
int p = 0;//从索引idx为0的结点开始遍历
for ( int i = 0; s[i] ; i ++){
int u = s[i] - 'a';//将a-z映射到0-9,将映射后的值保存至u
if ( !son[p][u]) son[p][u] = ++idx;//如果不存在下一个孩子,那么新建一个孩子,并将idx索引赋给这个孩子
p = son[p][u];//跳到下一个索引idx结点
}
cnt[p] ++;//计数当前的字符串
}

int query(char s[]){
int p = 0;//从索引idx为0的结点开始遍历
for ( int i = 0; s[i] ; i ++){
int u = s[i] - 'a';//将a-z映射到0-9,将映射后的值保存至u
if ( !son[p][u]) return 0;//如果不存在下一个孩子,代表没有这个字符串,返回0
p = son[p][u];//跳到下一个索引idx结点
}
return cnt[p];//返回这个字符串的个数
}

int main(){
int n;
cin >> n;
char op[2];
while ( n --){
scanf("%s%s",op, str);
if ( op[0] == 'I') insert(str);
else if ( op[0] == 'Q') printf("%d\n", query(str));
}

return 0;
}

【Tire树+贪心】拓展题

题目地址:143. 最大异或对 - AcWing题库

在给定的 NN 个整数 A1,A2……AN 中选出两个进行 xor(异或)运算,得到的结果最大是多少?

输入格式

第一行输入一个整数 N。

第二行输入 NN 个整数 A1~AN。

输出格式

输出一个整数表示答案。

数据范围

1≤N≤10^5
0≤Ai<2^31

输入样例:

1
2
3
1 2 3

输出样例:

1
3

【Trie数+贪心】算法设计

如下图:

image-20220109211039262

【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 <iostream>
#include <algorithm>

using namespace std;

const int N = 100010, M = 3000000;
int a[N];
int son[M][2], idx = 0;

void insert(int x){
int p = 0;
for ( int i = 30; i >= 0; i --){
int s = son[p][x >> i & 1];
if (!s) son[p][x >> i & 1] = ++idx;
p = son[p][x >> i & 1];
}
}

int query(int x){
int p = 0, res = 0;
for ( int i = 30; i >= 0; i --){
int s = x >> i & 1;
if ( son[p][!s]){
res += 1 << i;
p = son[p][!s];
}
else p = son[p][s];
}
return res;
}

int main(){
int n, res = 0;
cin >> n;
for ( int i = 0; i < n; i ++){
scanf("%d", &a[i]);
insert(a[i]);
}
for ( int i = 0; i < n; i ++){
res = max(res, query(a[i]));
}
cout << res;

return 0;
}

【Trie树+贪心】拓展题解析

对于每一个输入的数,转化为二进制后,当做一个“字符串”,比如数字6,转化为1101作为第一层的节点,因为题目要求异或之后的结果最大,对于数字6来说,如果仅考虑小于8的数,那么与数字6异或结果最大的那一个数,左边第一位应该为0,第二位为0,第三位为1,也就是110001= 111,对于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
#include <iostream>
#include <algorithm>

using namespace std;
/*
题目给的100000个数,因此N为1e5+10,
其中每个数的需要31位空间,有1e5个数,那么M就大概需要3*10^6那么大的数
*/
const int N = 100010, M = 3000000;
int a[N];
int son[M][2], idx = 0;

void insert(int x){
int p = 0;
for ( int i = 30; i >= 0; i --){//i从30开始遍历,代表移位的偏移量
int s = son[p][x >> i & 1];
/*
x >> i & 1表示x向右偏移i位,和1进行与运算,例如x为10,i为2,那么就是1010,
向右偏移两位,即为10,再与1与运算就是10&1=0
*/
if (!s) son[p][x >> i & 1] = ++idx;//同模板题,索引idx自增
p = son[p][x >> i & 1];//跳到下一个索引idx结点
}
}

int query(int x){
int p = 0, res = 0;
for ( int i = 30; i >= 0; i --){
int s = x >> i & 1;
if ( son[p][!s]){
/*
如果当前遍历的子节点的位和给定的x不同,那么就走不同的,例如x为10,也就是1010,
假设当前遍历到了第二位,如果是1,也就是和1010中第二位0不同,那么就选他
*/
res += 1 << i;
p = son[p][!s];
}
else p = son[p][s];//反之就只能选较差的那一个(因为能使和尽量大的数没有了)
}
return res;
}

int main(){
int n, res = 0;
cin >> n;
for ( int i = 0; i < n; i ++){
scanf("%d", &a[i]);
insert(a[i]);
}
for ( int i = 0; i < n; i ++){
res = max(res, query(a[i]));
}
cout << res;

return 0;
}