前言

本篇博客將介紹Trie樹的常見應用，包括：Trie字符串統計、最大異或對。首先，我們要知道Trie樹是什么？

Trie樹：是一種多叉樹的結構，每個節點保存一個字符，一條路徑表示一個字符串。例子：下圖表示了字符串： him 、 her 、 cat 、 no 、 nova 構成的 Trie 樹

Part 1：Trie字符串統計

1.題目描述

維護一個字符串集合，支持兩種操作：

1. I x 向集合中插入一個字符串 x；
2. Q x 詢問一個字符串在集合中出現了多少次。

共有 N 個操作，所有輸入的字符串總長度不超過 10⁵，字符串僅包含小寫英文字母。

輸入格式

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

接下來 N 行，每行包含一個操作指令，指令為 I x 或 Q x 中的一種。

輸出格式

對于每個詢問指令 Q x，都要輸出一個整數作為結果，表示 x 在集合中出現的次數。

每個結果占一行。

數據范圍

1≤N≤2?10⁴

輸入樣例

5
I abc
Q abc
Q ab
I ab
Q ab

輸出樣例

1
0
1

2.算法

• 用數組來模擬Trie樹
  

#include <iostream>using namespace std;const int N = 100010;
//son[][]存儲子節點的位置，分支最多26條；
//cnt[]存儲以某節點結尾的字符串個數（同時也起標記作用）
//idx表示當前要插入的節點是第幾個,每創建一個節點值+1
int son[N][26], cnt[N], 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];  //使“p指針”指向下一個節點}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];  //返回字符串出現的次數
}int main()
{int m;cin >> m;while(m--){char op[2];scanf("%s%s", op, str);if(*op == 'I') insert(str);else printf("%d\n", query(str));}return 0;
}

Part 2：最大異或對

1.題目描述

在給定的 N 個整數 A1，A2……AN 中選出兩個進行 xor（異或）運算，得到的結果最大是多少？

輸入格式

第一行輸入一個整數 N。

第二行輸入 N 個整數 A1～AN。

輸出格式

輸出一個整數表示答案。

數據范圍

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

輸入樣例

3
1 2 3

輸出樣例

3

2.算法

• 字典樹不單單可以高效存儲和查找字符串集合,還可以存儲二進制數字
• 將每個數以二進制方式存入字典樹,找的時候從最高位去找有無該位的異

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010;
//保存 Trie 樹
int son[N * 31][2];  
int n, idx;void insert(int x)
{int p = 0;//初始化指向根節點//從最高位開始，依次取出每一位for (int i = 31; i >= 0; i--){   // 取出當前位int u = x >> i & 1;//如果樹中不能走到當前數字//為當前數字創建新的節點，保存該數字if (!son[p][u])// 新節點編號為 idx + 1son[p][u] = ++idx; p = son[p][u];}
}int query(int x)
{//指向根節點int p = 0;// 保存與 x 異或結果最大的那個數int ret = 0;//從最高位開始，依次取出 x 的每一位for (int i = 31; i >= 0; i--){// 取出 x 的當前位int u = x >> i & 1;//如果樹中能走到 !u，就走到!uif (son[p][!u]){//走到!up = son[p][!u];//更新 x 異或的對象ret = ret * 2 + !u;}  //沒有!u，就只能走到u了else{p = son[p][u];//更新 x 異或的對象ret = ret * 2 + u; }}//計算異或結果ret = ret ^ x;return ret;
}int main()
{cin >> n;int maxXorNum = 0; int x;for (int i = 0; i < n; i++){cin >> x;insert(x);maxXorNum = max(maxXorNum, query(x));}cout << maxXorNum << endl;return 0;
}