字典树模板

字典树

预定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
const int N = 1e6+10;
int tot = 1;
struct node
{
int son[26];
int cnt; // 特殊标记
bool have;
node()
{
memset(son,0,sizeof son);
cnt = 0;
have = false;
}
}trie[N];

插入

1
2
3
4
5
6
7
8
9
10
11
12
13
void Insert(char *s)
{
int len = strlen(s);
int u = 0,v;
for(int i = 0;i < len;i++)
{
v = s[i]-'a';
if(!trie[u].son[v])
trie[u].son[v] = tot++;
u = trie[u].son[v];
}
trie[u].have = true;
}

查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int Find(char *s)
{
int len = strlen(s);
int u = 0,v;
for(int i = 0;i < len;i++)
{
v = s[i]-'a';
if(!trie[u].son[v])
return 0;
u = trie[u].son[v];
}
if(!trie[u].have) // 没有这个单词
return 0;
if(!trie[u].cnt) // 没被查询过
{
trie[u].cnt++;
return 1;
}
return 0;
}

注意

涉及到多组输入的时候可以这样处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
struct node
{
int son[26];
int cnt; // 特殊标记
bool have;
void clear
{
memset(son,0,sizeof son);
cnt = 0;
have = false;
}
}trie[N];

int main()
{
trie[0].clear();
}

01字典树

预定义

1
2
3
4
5
6
7
8
9
10
11
12
const int N = 1e6+100;
int tot = 1;
struct node
{
int son[2];
int size;
node()
{
memset(son,0,sizeof son);
size = 0;
}
}trie[32*N];

插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void Insert(int x)
{
int root = 1;
trie[root].size++;
for(int k = 30;k >= 0;k--)
{
int tmp = 0;
if(x & (1<<k))
tmp = 1;
if(!trie[root].son[tmp])
trie[root].son[tmp] = ++tot;
root = trie[root].son[tmp];
trie[root].size++;
}
}

删除

1
2
3
4
5
6
7
8
9
10
11
12
13
void Delete(int x)
{
int root = 1;
trie[root].size--;
for(int k = 30;k >= 0;k--)
{
int tmp = 0;
if(x & (1<<k))
tmp = 1;
root = trie[root].son[tmp];
trie[root].size--;
}
}

查询

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
int Query(int x)
{
int root = 1;
for(int k = 30;k >= 0;k--)
{
int tmp = 0;
if(x & (1<<k))
tmp = 1;
if(tmp)
{
if(trie[root].son[0] && trie[trie[root].son[0]].size)
root = trie[root].son[0];
else
root = trie[root].son[1],x ^= (1<<k);
}
else
{
if(trie[root].son[1] && trie[trie[root].son[1]].size)
root = trie[root].son[1],x ^= (1<<k);
else
root = trie[root].son[0];
}
}
return x;
}

习题

CF 706 D. Vasiliy’s Multiset

Chip Factory (ACM Changchun 2015)

HDU 4825 Xor Sum

求完美序列度(待解决)