【Trie树】字典树

参考博客

基本的Tire树

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;

const int maxn = 1e5 + 10;
const int sigmasize = 30;

struct Trie{
int ch[maxn][sigmasize];
int val[maxn];
int cnt;

Trie(){
cnt = 1;
memset(ch[0],0,sizeof(ch[0]));
}

int idx(char c){
return c - 'a';
}

void insert(char *s,int v){
int u = 0,n = strlen(s);
for(int i = 0;i < n;i++){
int c = idx(s[i]);
if(!ch[u][c]){ //create a new node
memset(ch[cnt],0,sizeof(ch[cnt]));
val[cnt] = 0;
ch[u][c] = cnt++;
}
u = ch[u][c];
}
val[u] = v;
}

bool find(char *s){
int u = 0,n = strlen(s);
for(int i = 0;i < n;i++){
int c = idx(s[i]);
if(ch[u][c] == 0)return false;
u = ch[u][c];
}
return true;
}
}

附上水题一枚

Phone List
链接

题意

给一组电话号码,问有没有某一个是其他的前缀,有的话无法正常拨通,如给 911,和9111421,则无法拨通第二个

代码
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
/*
Hdu-1671
*/


#include<bits/stdc++.h>
using namespace std;

int T,n,cnt;
bool flag;

const int maxn = 1e5 + 10;

int vis[maxn],pre[maxn],Tree[maxn][15];

void insert(string s){
int len = s.length();

int p = 1;

for(int i = 0;i < len;i++){
int c = s[i] - '0';
if(!Tree[p][c]){
Tree[p][c] = ++cnt; //create new node
}

p = Tree[p][c];
pre[p]++;

if(vis[p]){
flag = true;
break;
}
}
vis[p] = 1;
if(pre[p] > 1){
flag = 1;
}

}

int main(){
ios::sync_with_stdio(false);
cin >> T;
while(T--){
memset(vis,0,sizeof(vis));
memset(Tree,0,sizeof(Tree));
memset(pre,0,sizeof(pre));
flag = false;
cnt = 1;

cin >> n;
for(int i = 0;i < n;i++){
string s;
cin >> s;
if(!flag){
insert(s);
}
}
string s = flag ? "NO" : "YES";
cout << s << endl;
}
}

01字典树

按最大数字的二进制位的长度来确定树的高度,其余不足位数在之前用 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
struct Trie{
int ch[maxn][2];
int val[maxn];
int cnt;

Trie(){
cnt = 1;
memset(ch[0],0,sizeof(ch[0]));
}


void insert(int x){
int u = 0;
for(int i = maxlog;i >= 0;i--){
int c = (x & ( 1 << i )) >> i;
if(ch[u][c] == 0){
ch[u][c] = cnt++;
}
u = ch[u][c];
}
val[u] = 1;
}
};

异或问题

$x \oplus x = 0$
$a \oplus b = b \oplus a$
$x \oplus 0 = x$
根据自反性质,区间的异或值具有前缀性质,即

01字典树与最大异或值的问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int query(int x){
int ans = 0,u = 0;
for(int i = maxlog;i >= 0;i--){
int c = (x & (1 << i)) >> i;
if(ch[u][c^1]){
ans += (1<<i);
u = ch[u][c^1];
}
else{
u = ch[u][c];
}
}
return ans;
}

可持久化01字典树

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
struct Trie
{
int cnt;
int ch[maxn * 24][2], sum[maxn * 24];

inline int insert(int x, int val)
{
int o, y; o = y = ++cnt;
for(int i = 23; i >= 0; i--)
{
//复制儿子的所有相关信息
ch[y][0] = ch[x][0];
ch[y][1] = ch[x][1];
//更新位置计数
sum[y] = sum[x] + 1;
int c = (val & (1 << i)) >> i;
//新建结点
x = ch[x][c];
ch[y][c] = ++cnt;
y = ch[y][c];
}
sum[y] = sum[x] + 1;
return o;
}
inline int query(int l, int r, int val)//使用时应该用一个roor[l],root[r],类似主席树那样
{
int ans = 0;
for(int i = 23; i >= 0; i--)
{
int c = (val & (1 << i)) >> i;
//使用差值判断是否存在
if(sum[ch[r][c ^ 1]] - sum[ch[l][c ^ 1]])
{
ans = ans + (1 << i);
r = ch[r][c ^ 1];
l = ch[l][c ^ 1];
}
else
{
r = ch[r][c];
l = ch[l][c];
}
}
return ans;
}
}trie;