Tire樹（字典樹）

理論

在這里插入圖片描述
上圖是一棵Trie樹，表示了關鍵字集合{“a”, “to”, “tea”, “ted”, “ten”, “i”, “in”, “inn”} 。從上圖可以歸納出Trie樹的基本性質：

根節點不包含字符，除根節點外的每一個子節點都包含一個字符。
從根節點到某一個節點，路徑上經過的字符連接起來，為該節點對應的字符串。
每個節點的所有子節點包含的字符互不相同。
從第一字符開始有連續重復的字符只占用一個節點，比如上面的to，和ten，中重復的單詞t只占用了一個節點。

模板

//節點
struct Node {//每個節點有26個子節點Node* son[26]{};//末尾標記，可用于區分前綴字符串和完整字符串bool end = false;
};
class Tire {Node* root = new Node();int find(string s) {Node* cur = root;for (char c : s) {int t = c - 'a';if (cur->son[t] == nullptr) {//沒找到返回0return 0;}cur = cur->son[t];}//找到完整的返回2，前綴字符串返回1return cur->end ? 2 : 1;}
public://插入字符串void insert(string word) {Node* cur=root;for(char c:word){c-='a';if(cur->son[c]==nullptr){cur->son[c]=new Node();}cur=cur->son[c];}cur->end=true;}//查詢完整字符串bool search(string word) {return find(word)==2;}//查詢前綴字符串bool startsWith(string prefix) {return find(prefix)!=0;}
};

例題

例題1

愛找事的小Z
題目描述:
小 Z 同學非常喜歡找事，現在有很多名為“事”的字符串，現在小 Z 想要找“事”，請你幫助他判斷，他今天是否找了兩件相同的事。
輸入描述
輸入第一行包含一個整數 n，表示小 Z 今天找了多少事。
接下來 n行分別表示 n 件事。
事的輸入量不超過 1e3,每個"事"字符串的長度不超過 1000，且所有字母均為小寫。
輸出描述
若有相同的事輸出1，否則輸出0。
輸入輸出樣例
示例1
輸入

12
acd
acd
asdfsdf
asd
f
saf
asdf
sfasdfs
f
asdf
asf
asdfs

輸出

示例2
輸入

21
adfasdfaasdf
asdfsfas
fa
sdfasd
fsd
fs
a
sda
fsd
afasd
f
sda
f
asdf
as
df
sda
gggggas
dfdsfe
def
a

輸出

示例
輸入

9
asdfasdfa
asdfb
asdc
fasd
fde
sadf
fg
hsadfasdfasdg
iggsadffsa

輸出

#include<bits/stdc++.h>
using namespace std;
//節點
struct Node {//每個節點有26個子節點Node* son[26]{};//末尾標記，可用于區分前綴字符串和完整字符串bool end = false;
};
class Tire {Node* root = new Node();int find(string s) {Node* cur = root;for (char c : s) {int t = c - 'a';if (cur->son[t] == nullptr) {//沒找到返回0return 0;}cur = cur->son[t];}//找到完整的返回2，前綴字符串返回1return cur->end ? 2 : 1;}
public://插入字符串void intsert(string s) {Node* cur = root;for (char c : s) {int t = c - 'a';if (cur->son[t] == nullptr) {cur->son[t] = new Node();}cur = cur->son[t];}cur->end = true;}//查詢字符串bool  check(string s) {return find(s) == 2;}
};
int main() {Tire tire;int n;cin >> n;int ans = 0;for (int i = 1; i <= n; i++) {string temp;cin >> temp;if (!tire.check(temp)) {tire.intsert(temp);}else {ans++;}}if (ans) {cout << 1;}else {cout << 0;}return 0;
}

例題2

小藍的神秘圖書館
問題描述
小藍是圖書館的管理員，他負責管理圖書館的所有書籍。圖書館有 N本書，每本書都有名字，分別為 S1,S2,…,SN。
圖書館的讀者們經常來詢問小藍，他們會給小藍一個字符串 T，希望小藍能告訴他們，圖書館里有多少本書的名字是以 T的前綴開頭的。小藍需要回答他們 M次這樣的詢問。
現在，小藍需要你的幫助。你能幫助小藍解決這個問題，從而提升圖書館的服務質量嗎？
輸入格式
第一行輸入兩個整數 N 和 M（1≤N,M≤1e4）。
接下來 N 行，每行輸入一個字符串 Si，表示圖書館中的一本書的名字。
接下來 M行，每行一個字符串 T，表示讀者的詢問。
輸入字符串的總長度不超過 2×1e5，且僅包含小寫字母。
輸出格式
對于每個詢問，輸出一個整數，表示圖書館中以字符串 T開頭的書的數量。
每個答案占一行。
樣例輸入

5 2
ababc
ababd
aba
ab
a
abab
ccc

樣例輸出

2
0

#include<bits/stdc++.h>
using namespace std;
struct Node {Node* son[26];int end = 0;
};
class Tire {Node* root = new Node();int dfs(Node* cur) {int res = 0;if (cur == nullptr) {return res;}if (cur->end) {res += cur->end;}for (int i = 0; i < 26; i++) {if (cur->son[i]) {res+=dfs(cur->son[i]);}}return res;}
public:void insert(string s) {Node* cur = root;for (char c : s) {c = c - 'a';if (cur->son[c] == nullptr) {cur->son[c] = new Node();}cur = cur->son[c];}cur->end++;}int find(string s) {Node* cur = root;for (char c : s) {c = c - 'a';if (cur->son[c] == nullptr) {return 0;}cur = cur->son[c];}return dfs(cur);}
};
int main() {Tire tire;int n, m;cin >> n >> m;for (int i = 1; i <= n; i++) {string s;cin >> s;tire.insert(s);}for (int i = 1; i <= m; i++) {string s;cin >> s;cout << tire.find(s) << '\n';}return 0;
}

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e5 + 10;
string str[N],s[N];
ll n = 0, m = 0;
ll trie[N][27], cnt[N];
ll idx = 2;
void insert(string a){ll p = 1;ll k = a.length() - 1;for (ll i = 1; i <= k; i++){if (!trie[p][a[i] - '0']) trie[p][a[i] - '0'] = idx++;p = trie[p][a[i] - '0'];cnt[p]++;}
}
ll query(string a){ll p = 1;ll k = a.length() - 1;ll ans = 0x3f3f3f;for (ll i = 1; i <= k; i++){p = trie[p][a[i] - '0'];ans = min(ans, cnt[p]);}return ans;
}
int main(){ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);cin >> n >> m;for (ll i = 1; i <= n; i++){cin >> str[i];str[i] = '0' + str[i];insert(str[i]);}for (ll i = 1; i <= m; i++){cin >> s[i];s[i] = '0' + s[i];cout << query(s[i]) << endl;}return 0;
}

01Tire

理論

在這里插入圖片描述
x >> i & 1
(010)>>30 → (000)&(001) → 0
……
(010)>>2 → (000)&(001) → 0
(010)>>1 → (001)&(001) → 1
(010)>>0 → (010)&(001) → 0

1 << i
(001)<<2 → (100) → 4
(001)<<1 → (010) → 2
(001)<<0 → (001) → 1

res |= (1<< i)
(010)^(101) → (111) → 4+2+1=7
(011)^(101) → (110) → 4+2+0=6
(101)^(010) → (111) → 4+2+1=7
(111)^(010) → (101) → 4+0+1=5

模板

const int N = 1e5 + 10;
int son[32 * N][2], tot = 1;
//插入
void insert(int x)
{int o = 1;for (int i = 30; i >= 0; --i){int y = x >> i & 1;if (!son[o][y])son[o][y] = ++tot;o = son[o][y];}
}//查詢
int query(int x)
{int o = 1, res = 0;for (int i = 30; i >= 0; --i){int y = x >> i & 1;//找相反方向的，0找1，1找0，異或后為1，大小最大if (son[o][!y])o = son[o][!y], res |= (1ll << i);//如果該方向沒有，則按原有方向走elseo = son[o][y];}return res;
}

例題

XOR最大值
問題描述
給定一個整數數組 arr 和一個整數 q 表示查詢的數量。接下來的 q行，每行給出一個整數 x。對于每個 x，你需要找到 arr 中的一個數 y使得 xXORy的值最大，然后輸出這個最大值。
輸入格式
第一行包含一個整數 n，表示數組 arr 的大小。
第二行包含 n個整數，分別是 arr的元素。(0≤arr[i]≤1e9)。
第三行包含一個整數 q，表示查詢的數量。
接下來的 q行，每行包含一個整數 x。(0≤x≤1e9)。
輸出格式
對于每個查詢輸出一行，表示 xXORy 的最大值。
樣例輸入

5
3 5 7 10 12
3
3
7
10

樣例輸出

15
13
15

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int son[32 * N][2], tot = 1;void insert(int x)
{int o = 1;for (int i = 30; i >= 0; --i){int y = x >> i & 1;if (!son[o][y])son[o][y] = ++tot;o = son[o][y];}
}int query(int x)
{int o = 1, res = 0;for (int i = 30; i >= 0; --i){int y = x >> i & 1;if (son[o][!y])o = son[o][!y], res |= (1ll << i);elseo = son[o][y];}return res;
}int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int n;cin >> n;for (int i = 1; i <= n; ++i){int x;cin >> x;insert(x);}int q;cin >> q;while (q--){int x;cin >> x;cout << query(x) << "\n";}
}

#include<bits/stdc++.h>
using namespace std;
struct Node {Node* son[2]{};
};
class Tire {Node* root = new Node();
public:void insert(int x) {Node* cur = root;for (int i = 30; i >= 0; i--) {int y = x >> i & 1;if (!cur->son[y]) {cur->son[y] = new Node();}cur = cur->son[y];}}int query(int x) {Node* cur = root;int res = 0;for (int i = 30; i >= 0; i--) {int y = x >> i & 1;if (cur->son[!y]) {res = res + (1 << i);cur = cur->son[!y];}else {cur = cur->son[y];}}return res;}
};
int main() {Tire tire;ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int n;cin >> n;for (int i = 1; i <= n; ++i){int x;cin >> x;tire.insert(x);}int q;cin >> q;while (q--){int x;cin >> x;cout << tire.query(x) << "\n";}return 0;
}