Trie树

Trie树是什么？

在计算机科学中，trie，又称前缀树或字典树，是一种有序树，用于保存关联数组，其中的键通常是字符串。

Trie树可以用于高效的存储字符串集合，并且可以很快的查找某个字符串是否在集合中出现过或在集合中出现的次数。

Trie树的基本性质 （1）根节点不包含字符，除了根节点之外，每个节点包含一个字符 （2）根节点到一个子节点为这个子节点所存储的字符串 （3）每个节点的所有子节点连接起来的字符串各不相同

下面我们来说一下这道题如何去实现

（题目中的数据范为2*10^5 ， 定义const int N = 1e5 + 10 ， 1e5为科学计数法，+10是为了保险起见） 首先我们需要使用一个二维数组 son[N][26] 来存储我们的Trie树，因为只有小写英文字母26个，所以第二维度的大小定义为26即可。

我们还需要一个唯一的变量 idx 来存储我们的节点。

在存储完一个字符串的时候，取到他的唯一的下标 idx ， 用一个一维数组来记录这个字符串出现的次数。

下面就来看一下是如何实现的把。

835. Trie字符串统计 ​

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

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

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

输入格式

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

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

输出格式

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

每个结果占一行。

数据范围

1≤N≤2∗1041≤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 = 1e5 + 10; int n , cnt[N]; char str[N]; // idx下标将 Trie树 中的节点连接起来. int son[N][26] , idx; // 向 Trie树 中插入字符串 void insert(char *str) { // 每次都从根节点开始遍历 int p = 0; for(int i = 0 ; str[i] ; i++) { // 取到在二维数组中存储的第二维度的下标 // 比如说 p=0的话,如果是 int u = str[i] - 'a'; if(!son[p][u]) son[p][u] = ++idx; p = son[p][u]; } // 插入后 , 该字符串计数+1 cnt[p] ++; } // 在 Trie树 中查询字符串出现的次数 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]; } int main() { scanf("%d" , &n); // n 次询问 while(n--) { char op[2]; scanf("%s%s" , op , str); if(*op == 'I') insert(str); else printf("%d\n" , query(str)); } cout << "\n\n\n"; for(int i = 0 ; i <= 20 ; i++) { for(int j = 0 ; j < 26 ; j++) { cout << son[i][j] << ' '; } cout << endl; } return 0; }

836. 最大异或对

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

输入格式

第一行输入一个整数N。

第二行输入N个整数A1A1～ANAN。

输出格式

输出一个整数表示答案。

数据范围

1≤N≤1051≤N≤105, 0≤Ai<2310≤Ai<231

输入样例：

3 1 2 3

输出样例：

3 #include <iostream> using namespace std; const int N = 1e5 + 10 , M = 3e6 + 10; int n , a[N] , son[M][2] , idx; // 向 Trie树 中插入数据 void insert(int x) { int p = 0; // int类型数据有32位,最高位是符号位,所以数据位有31位 // 要求出最大的异或对,所以从最高位开始计算 for(int i = 30 ; i >= 0 ; i--) { // x >> i & 1 可以求出 x 的第i位是1或0 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; // 求异或, 0 和 1 异或值才最大,所以如果第i位是1的话,优先去判断0的位置是否有值 if(son[p][!s]) { // 将值向左移 i 位之后,使用res记录下来 res += 1 << i; p = son[p][!s]; }else { p = son[p][s]; } } return res; } int main() { scanf("%d" , &n); for(int i = 0 ; i < n ; i++) { scanf("%d" , &a[i]); insert(a[i]); } int res = 0; for(int i = 0 ; i < n ; i++) res = max(res , search(a[i])); printf("%d" , res); }