【字典樹/trie樹】實(shí)現(xiàn)高效插入和查詢字符串的數(shù)據(jù)結(jié)構(gòu)
本文是https://www.acwing.com/problem/content/description/837/的總結(jié)，有興趣可以做做
字典樹的實(shí)現(xiàn)依賴于樹結(jié)構(gòu)，有兩種操作，1是插入字符串，2是查找字符串。使用idx維護(hù)最新的結(jié)點(diǎn)下標(biāo)。如下圖，假設(shè)我們維護(hù)一個
可以看到，我們維護(hù)了一個樹形結(jié)構(gòu)儲存了左邊的字符串，但是我們不止建立這樣的樹，還得標(biāo)記每個字符串的結(jié)尾
這樣，當(dāng)我們多次插入像ab這樣的字符串的時候就可以記錄下插入的總數(shù)。我們將每個結(jié)點(diǎn)都標(biāo)記一個編號，根結(jié)點(diǎn)標(biāo)記為0，起全局變量idx實(shí)現(xiàn)。具體代碼實(shí)現(xiàn)如下：
1 #include<bits/stdc++.h> 2 #define int long long 3 using namespace std; 4 const int INF = 1e18 + 10,maxn = 1e5 + 10; 5 6 int n; 7 int son[maxn][26],idx,cnt[maxn]; 8 9 void insert(char str[]){ 10 int p = 0; 11 for(int i = 0; str[i] ; i++){ 12 int id = str[i] - 'a'; 13 if(!son[p][id]) son[p][id] = ++idx; 14 p = son[p][id]; 15 } 16 cnt[p]++; 17 } 18 19 int quary(char str[]){ 20 int p = 0; 21 for(int i = 0; str[i]; i++){ 22 int id = str[i] - 'a'; 23 if(!son[p][id]) return 0; 24 p = son[p][id]; 25 } 26 return cnt[p]; 27 } 28 signed main (){ 29 ios::sync_with_stdio(false); 30 cin.tie(0),cout.tie(0); 31 32 cin>>n; 33 char str[maxn]; 34 for(int i = 1; i <= n; i++){ 35 char op; 36 cin>>op; 37 cin>>str; 38 if(op == 'I'){ 39 insert(str); 40 }else if(op == 'Q'){ 41 cout << quary(str) << '\n'; 42 } 43 } 44 45 return 0; 46 }
在這里解釋以下數(shù)據(jù)結(jié)構(gòu)作用
son[i][id]//表示結(jié)點(diǎn)i的兒子id是否存在。（還記得嗎，我們使用idx給每個結(jié)點(diǎn)編號）
idx//當(dāng)更新結(jié)點(diǎn)時++idx，賦予新建立的結(jié)點(diǎn)獨(dú)一無二的編號。
cnt[i]//表示以結(jié)點(diǎn)i結(jié)尾的字符串的數(shù)量，相當(dāng)于上圖中給每個字符串結(jié)尾標(biāo)記。
浙公網(wǎng)安備 33010602011771號