一、定義與結構

? 用來快速存儲查找字符串集合的一種數據結構

將字符串按順序連接根節點上，并在字符串結束的地方打上標記并計數。?

二、模板題

acwing 835 Trie?樹的字符串統計

題目：

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

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

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

輸入格式

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

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

輸出格式

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

每個結果占一行。

數據范圍

1≤N≤2?10^4

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int cnt[N], son[N][26], idx;/*cnt表示字符串的個數
son 前一維表示父節點，后一維表示子節點 idx表示當前用到了哪個下標，下標為零的點，即是根節點，也是空節點*/
char str[N];void insert(char s[])//存儲字符串，構建字典樹
{int p = 0;for (int i = 0; s[i]; i ++ )//字符串最后一位為“/0”所以可以做for循環中的結束條件{int u = s[i] - 'a';//用數字表示所有小寫字母if (!son[p][u])  son[p][u] = ++ idx;//如果沒有子節點，創建新的節點p = son[p][u];//移動到下一個節點，繼續}cnt[p] ++ ;//字符串數量++
}int query(char s[])//統計字符串的個數
{int p = 0;for (int i = 0; s[i]; i ++ ){int u = s[i] - 'a';if (!son[p][u])  return 0;//沒有符合條件的字符串，結束p = son[p][u];//有則繼續}return cnt[p];
}int main()
{int n;scanf("%d", &n);while (n -- ){char op[5];scanf("%s%s", op, str);if (*op == 'I') insert(str);else    printf("%d\n", query(str));}return 0;
}

2.acwing143最大異或對

題目

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

輸入格式

第一行輸入一個整數?N。

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

輸出格式

輸出一個整數表示答案。

數據范圍

1≤N≤10^5
0≤Ai<2^31

/*字典樹不僅可以存儲字符串也可以存儲二進制數字*/
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,M=31*N;
int son[M][2],idx;
void insert(int x)
{int p=0;for(int i=30;i>=0;i--){int u=x>>i&1;//u代表x的二進制中的第i位數字if(!son[p][u])son[p][u]=++idx;p=son[p][u];}
}
int query(int x)
{int p=0,t=0;//保存與x異或結果最大的數for(int i=30;i>=0;i--)//從最高位取出每一位{int u=x>>i&1;if(son[p][!u])//如果樹中能走到！u就走到!u.{t=(t<<1)+!u;//更新x異或的對象p=son[p][!u];//走到!u}else {t=(t<<1)+u;p=son[p][u];}}return t;
}
int main()
{int n,ans=0;cin>>n;while(n--){int x;cin>>x;insert(x);int t=query(x);ans=max(ans,x^t);}cout<<ans<<endl;return 0;
}