字典trie模板

发表于 | 更新于

标准版

含义详解

a[p][ch]的值为下一个节点的层数，即idx(第几个节点)，ch为字符指针配合p
即可确定节点所在的具体层数与位置(N为所有字符串总长度，每层26个节点)
a[p][ch]第一维共N 26个节点， idx最大为N 26 - 1
通过 p = a[p][ch]来实现更新指向下一个节点

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
const int N =  ;
int a[N][26], idx;		//根节点在第0层 
char str[N];
bool end[N];		//结束数组(在最后一个元素下一层)
void insert()
{
	int p = 0;		//根节点为 0， p为在树中的层数 
	for(int i = 0; str[i]; i ++ )		
	{
		char ch = str[i] - 'a';		//ch为字符指针 
		if(!a[p][ch]) 	a[p][ch] = ++ idx;		
			//字符指针指向空，创建节点(a[p][ch]的值为下一层，即字符指针指向的地方)，新节点
		p = a[p][ch];	//变换到下一个节点(下一层) 
	}
	end[p] = true;		//结束标记，下一层的位置标记true 
}

bool search()
{
	int p = 0;	//根节点，p为层数 
	for(int i = 0; str[i]; i ++ )
	{
		char ch = str[i] - 'a';		//字符指针 
		if(!a[p][ch]) 	return false;		//指向空，返回false 
		p = a[p][ch];		//节点变换到下一个(下一层) 
	} 
	return end[p];	//整个字符串成功便利，判断是否有结束标记 
}

例题一: 前缀统计

给定N个字符串S1,S2…SN，接下来进行M次询问，每次询问给定一个字符串T，求S1～SN中有多少个字符串是T的前缀。

输入字符串的总长度不超过106，仅包含小写字母。

输入格式

第一行输入两个整数N，M。

接下来N行每行输入一个字符串Si。

接下来M行每行一个字符串T用以询问。

输出格式

对于每个询问，输出一个整数表示答案。

每个答案占一行。

输入样例：

1
2
3
4
5
6
3 2
ab
bc
abc
abc
efg

输出样例：

1
2
2
0

题意分析

对前n个字符串进行建树，即插入树的insert()操作，对于后m个字符进行search()操作, 判断每个给出的字符串str在n中有多少个为
str的前缀。
细节处理
end[p] -> 变为cnt[p]，从0 1变为统计次数，查询时sum += cnt[p], 遇到a[p][ch]指向空则break
退出for循环后 return sum

代码

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 <iostream>
#include <algorithm>
using namespace std;
const int N = 500000, M = 1000010;
int a[N][26], idx, cnt[N];
char str[N];
void insert()
{
    int p = 0;
    for(int i = 0; str[i]; i ++ )
    {
        int ch = str[i] - 'a';
        if(!a[p][ch])   a[p][ch] = ++ idx;
        p = a[p][ch];		
    }
    cnt[p] ++;			//变为统计次数
}

int search()
{
    int p = 0, sum = 0;
    for(int i = 0; str[i]; i ++ )
    {
        int ch = str[i] - 'a';
        if(!a[p][ch])   break;			//没查询到，退出返回，可能为0或正数
        p = a[p][ch];       
        sum += cnt[p];
    }
    return sum;
}

int main()
{
    int n, m;
    cin >> n >> m;
    while(n -- )			//前n个插入操作
        scanf("%s", str), insert();
    while(m -- )			//后m个查询n中有多少个为str的前缀
    {
        scanf("%s", str);
        cout << search() << endl;
    }
    return 0;
}

例题二: 最大异或对

在给定的N个整数A1，A2……AN中选出两个进行xor（异或）运算，得到的结果最大是多少？

输入格式

第一行输入一个整数N。

第二行输入N个整数A1～AN。

输出格式

输出一个整数表示答案。

数据范围

1≤N≤105,
0≤Ai<231

输入样例：

1
2
3
1 2 3

输出样例：

3

题意分析

将每个A_i视为一个31位的01串，对这n个数进行建树依次insert($A_i$)，共有N * 32个节点，每个节点为0 1其中之一
之后对每个串进行查询操作，由于是异或，则应每次判断是否存在num相异的节点，存在则 p = a[p][!num]更新，
res对应位变为1(xor相异结果为true)不存在则按原来更新p = a[p][num], 但res此时对应位不做改变

代码

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
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 100005;
int trie[N * 32][2], a[N], idx;	//共可能存在N * 32个节点，每个节点0 1两种情况, idx为节点下标
void insert(int x)			//建树(插入)
{
    int p = 0;
    for(int i = 30; ~i; i -- )		//从高位到低位遍历0 1串
    {
        int num = x >> i & 1;
        if(!trie[p][num])  trie[p][num] =  ++ idx;
        p = trie[p][num];
    }
}

int search(int x)			//查询
{
    int p = 0, res = 0;
    for(int i = 30; ~i; i -- )
    {
        int num = x >> i & 1;
        if(trie[p][!num])   			//查询反向num值节点是否存在
            p = trie[p][!num], res |= 1;
        else
            p = trie[p][num];		//不存在则原样更新
        if(i)
            res <<= 1;			//每次向左挪一位
    }
    return res;
}
int main()
{
    int n, x, ans = 0;
    cin >> n;
    for(int i = 0; i < n; i ++ )
    {
        scanf("%d", &a[i]);
        insert(a[i]);   
    }
    for(int i = 0; i < n; i ++ )
        ans = max(ans, search(a[i]));
    cout << ans << endl;
    return 0;
}
0%