Trie 树

基本用法

高效的存储和查找字符串集合的数据结构

模板

int son[N][26], cnt[N], idx;
// 0号点既是根节点，又是空节点
// son[][]存储树中每个节点的子节点
// cnt[]存储以每个节点结尾的单词数量

// 插入一个字符串
void insert(char *str)
{
    int p = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';
        if (!son[p][u]) son[p][u] = ++ idx;
        p = son[p][u];
    }
    cnt[p] ++ ;
}

// 查询字符串出现的次数
int query(char *str)
{
    int p = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';
        if (!son[p][u]) return 0;
        p = son[p][u];
    }
    return cnt[p];
}

Trie字符串统计

维护一个字符串集合，支持两种操作：

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

共有N个操作，输入的字符串总长度不超过 105，字符串仅包含小写英文字母。

输入格式

第一行包含整数N，表示操作数。

接下来N行，每行包含一个操作指令，指令为”I x”或”Q x”中的一种。

输出格式

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

每个结果占一行。

数据范围

1≤N≤2∗104

输入样例：

5
I abc
Q abc
Q ab
I ab
Q ab

输出样例：

1
0
1

代码样例

#include<iostream>
using namespace std;
const int N=100010;
int son[N][26],cnt[N];
int idx;
char str[N];

void insert(char str[])
{
	int p=0;
	// 遍历字符串 
	for(int i=0;str[i];i++)
	{
		// 将小写字母映射成数字 
		int u=str[i]-'a';
		// 若当前节点不存在这个字母，则创建新节点 
		if(!son[p][u]) son[p][u]=++idx;
		// 最后的节点 
		p=son[p][u];
	}
	cnt[p]++;
}

int query(char str[])
{
	int p=0;
	for(int i=0;str[i];i++)
	{
		int u=str[i]-'a';
		// 若不存当前字母的节点则直接返回 0  
		if(!son[p][u]) return 0;
		// 最后的节点 
		p=son[p][u];
	}
	// 返回字符串的数量 
	return cnt[p];
}

int main()
{
	int n;
	cin>>n;
	while(n--)
	{
		char op[2];
		cin>>op>>str;
		if(op[0]=='I') insert(str);
		else cout<<query(str)<<endl;
	} 
	 return 0;
 } 

143. 最大异或对

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

输入格式

第一行输入一个整数 N。

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

输出格式

输出一个整数表示答案。

数据范围

1≤N≤10⁵,
0≤A_i<2³¹

输入样例：

3
1 2 3

输出样例：

3

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<stack>
#include<queue>
#include<sstream>
#include<map>

#define x first
#define y second

using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 3000010;
const int MOD = 1000000007;
const int INF = 0x3f3f3f3f;

int gcd(int a, int b){return b ? gcd(b, a % b) : a;}
int lowbit(int x) {return x & -x;}

int n;
int a[N], son[N][2], idx;

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

int search(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()
{
	cin >> n;
	for(int i = 0; i < n; i ++ ){
		cin >> a[i];
		insert(a[i]);
	}
	
	int res = 0;
	for(int i = 0; i < n; i ++ ) res = max(res, search(a[i]));
	
	cout << res << endl;

	return 0;
}