【定義】
字典樹（TrieTree），是一種樹形結(jié)構(gòu)，典型應(yīng)用是用于統(tǒng)計(jì)，排序和保存大量的字符串（但不僅限于字符串,如01字典樹）。
主要思想是利用字符串的公共前綴來節(jié)約存儲(chǔ)空間。很好地利用了串的公共前綴，節(jié)約了存儲(chǔ)空間。字典樹主要包含兩種操作，插入和查找。
通常在每個(gè)字符串結(jié)尾的地方標(biāo)記，這樣查找的時(shí)候只要找到了字符串中的每個(gè)字符且最后一個(gè)字符有標(biāo)記，就說明存在；反之，即使找到了要查找的字符串的每一個(gè)字符，但結(jié)尾字符的位置沒有標(biāo)記，也屬于沒有找到。
模板題 Trie字符串統(tǒng)計(jì)
【分析】
1.需要用到的
(1) idx：當(dāng)前用到的點(diǎn)的下標(biāo)（類似于單鏈表存儲(chǔ)）
(2) cnt [i] ：以i結(jié)尾的字符串個(gè)數(shù)
(3) 變量p：p代表查詢與插入時(shí)的不斷變化的當(dāng)前節(jié)點(diǎn)編號(hào)，初始化為0，代表初始節(jié)點(diǎn)。
在函數(shù)的循環(huán)中，我們首先用x確定接下來要找的字母，再通過變量x確定了接下來我們需要查找當(dāng)前節(jié)點(diǎn)下是否有連接著目標(biāo)字母的節(jié)點(diǎn)。
通過每次確定的x，我們通過son[p][u] 查找連著目標(biāo)字母的節(jié)點(diǎn)的編號(hào)，如果目標(biāo)節(jié)點(diǎn)存在，就把p更新成目標(biāo)節(jié)點(diǎn)的編號(hào)（p = son[p][u]）；
如果son[p][u] == 0，代表字典樹中沒有這個(gè)點(diǎn)，如果是查找就代表沒有這個(gè)單詞，查找失敗。
而如果是插入函數(shù)，我們就用 ++idx 來把這個(gè)點(diǎn)存進(jìn)字典樹。在兩個(gè)函數(shù)的最后，用cnt[p]來標(biāo)記節(jié)點(diǎn)或返回節(jié)點(diǎn)值。
2.下標(biāo)是0的點(diǎn)既是根節(jié)點(diǎn)，又是空節(jié)點(diǎn)
重慶分公司
重慶分公司
#includeusing namespace std;
const int N=100010;
int son[N][26],cnt[N],idx;//cnt：以某點(diǎn)結(jié)尾的字符串個(gè)數(shù)
char str[N];
void insert(char str[]){
int p=0;//從根節(jié)點(diǎn)開始
for(int i=0;str[i];i++){
int u=str[i]-'a';//將字母a~z轉(zhuǎn)換成數(shù)字0~25
if(!son[p][u]) son[p][u]=++idx;//如果不存在，就另開一個(gè)
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];
}
int main(){
int n;
cin>>n;
while(n--){
char op[2];
scanf("%s%s",op,str);
if(op[0]=='I') insert(str);
else cout< 例題 大異或?qū)?/p>
【分析】
1.主要思路：將每個(gè)數(shù)以二進(jìn)制方式存入字典樹,找的時(shí)候從最高位去找有無該位的異。
2.insert()
和上面基本是一樣的，但因?yàn)橐远M(jìn)制存儲(chǔ)，我們需要取x的第i位的二進(jìn)制數(shù)是什么（ u=x>>i&1），注意遍歷時(shí)從最高位開始（30~0剛好是31位）。
3.query()
同樣從最高位開始取u，然后在當(dāng)層尋找是否存在與u對(duì)應(yīng)的值
如果u==1，那么如果能夠在當(dāng)層找到某個(gè)節(jié)點(diǎn)的值為0，前二者就能夠進(jìn)行異或運(yùn)算；
如果u==0，那么如果能夠在當(dāng)層找到某個(gè)節(jié)點(diǎn)的值為1，前二者就能夠進(jìn)行異或運(yùn)算。
這樣最后得到的結(jié)果res左移一位之后還需加上異或的結(jié)果1（res=res*2+1）。
如果不能找到，res直接左移一位即可（res=res*2）。
4.最后，對(duì)于每一次尋找取大值（ res=max( res,query (a[i]) ) ）
【代碼】
#includeusing namespace std;
const int N=1e5+10,M=31*N;
int son[M][2],a[N];//M代表一個(gè)數(shù)字串二進(jìn)制可以到多長
int idx;
void insert(int x){
int p=0;
for(int i=30;i>=0;i--){
int u=x>>i&1;
if(!son[p][u]) son[p][u]=++idx;
p=son[p][u];
}
}
int query(int x){
int p=0,res=0;
//從最高位開始找
for(int i=30;i>=0;i--){
int u=x>>i&1;
if(son[p][!u]){
p=son[p][!u];
res=res*2+1;
}//該層存在與某某對(duì)應(yīng)的節(jié)點(diǎn)，就令p指向該節(jié)點(diǎn)，同時(shí)res左移一位并加上該點(diǎn)異或的值1
else {
p=son[p][u];
res=res*2;
}//否則正常進(jìn)行
}
return res;
}
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
insert(a[i]);//插入數(shù)據(jù)
}
int res=0;
for(int i=1;i<=n;i++){
res=max(res,query(a[i]));
}//取大值
cout< 練習(xí)1 模擬散列表
【分析】
其實(shí)是上面兩種情況的綜合
因?yàn)閿?shù)據(jù)大小在 -1e9~1e9 之間，所以每次操作我們都令x+=1e9，保證不出現(xiàn)負(fù)數(shù)而又沒有超限，并且數(shù)據(jù)達(dá)到32位，數(shù)組大小應(yīng)為son[ N *32][2]。
然后用二進(jìn)制存儲(chǔ)x，直接查找是否存在即可。
【代碼】
#includeusing namespace std;
const int N=1e5+10;
int son[N*32][2],idx;
int n;
void insert(int x){
int p=0,u;
for(int i=31;i>=0;i--){//31~0 三十二位
u=x>>i&1;
if(!son[p][u]) son[p][u]=++idx;
p=son[p][u];
}
}
int query(int x){
int p=0,u;
for(int i=31;i>=0;i--){
u=x>>i&1;
if(!son[p][u]) return 0;
p=son[p][u];
}
return 1;//存在
}
int main(){
cin>>n;
while(n--){
int x;
char op[2];
cin>>op;
if(op[0]=='I'){
cin>>x;
x+=1e9;
insert(x);
}
else{
cin>>x;
x+=1e9;
if(query(x)) puts("Yes");
else puts("No");
}
}
return 0;
} 練習(xí)2 P2850 錯(cuò)誤的點(diǎn)名
雖然但是，我還沒搞完。
你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧
