字典树（trie树）

acwing: https://www.acwing.com/problem/content/837/

在集合中插入字符串，询问字符串在集合中出现了多少次。

#include 
using namespace std;
const int N = 1e5 + 10;
int n, trie[N][26], cnt[N], idx;
char s[N];
void insert(char s[]){
	int u = 0;
	for (int i = 0; s[i]; i ++ ){
		int v = s[i] - 'a';
		if (!trie[u][v]) trie[u][v] = ++ idx;
		u = trie[u][v];
	}
	cnt[u] ++;
}
int query(char s[]){
	int u = 0;
	for (int i = 0; s[i]; i ++ ){
		int v = s[i] - 'a';
		if (!trie[u][v]) return 0;
		u = trie[u][v];
	}
	return cnt[u];
}
int main(){
	cin >> n;
	for (int i = 1; i <= n; i ++ ){
		char op[2];
		cin >> op >> s;
		if (op[0] == 'I') insert(s);
		else cout << query(s) << "\n";
	}
	return 0;
}

acwing: https://www.acwing.com/problem/content/145/

\(n\) 个数，从中选两个进行异或运算，求最大值

#include 
using namespace std;
const int M = 3e6 + 10;
int n, trie[M][2], idx, ans;
void insert(int x){
	int u = 0;
	for (int i = 30; ~ i; i -- ){// ~ i 等价于 i >= 0 
		int &v = trie[u][x >> i & 1];
		if (!v) v = ++ idx;
		u = v;
	}
}
int query(int x){
	int res = 0, u = 0;
	for (int i = 30; ~ i; i -- ){
		int v = x >> i & 1;
		if (trie[u][!v]){
			res += (1 << i);
			u = trie[u][!v];
		}
		else
			u = trie[u][v];
	}
	return res;
}
int main(){
	cin >> n;
	vector  a(n);
	for (int i = 0; i < n; i ++ ){
		cin >> a[i];
		insert(a[i]);
	}
	for (int i = 0; i < n; i ++ )
		ans = max( ans, query(a[i]) );
	cout << ans << "\n";
	return 0;
}

luogu：https://www.luogu.com.cn/problem/P8306

给定 \(n\) 个模式串 \(s_1, s_2, ..., s_n\) 和 \(q\) 次询问，每次询问给定一个文本串 \(t_i\)，问它是多少个模式串的前缀。

#include 
using namespace std;
int T, n, q;
string s;
struct Node{
	int cnt = 0;
	unordered_map < char, Node*> ch;
	void dfs(){
		for (auto [x, y] : ch){
			y -> dfs();
			cnt += y -> cnt;
		}
	}
};
Node *root;
void insert(string s){
	auto u = root;
	for (auto c : s){
		if (u -> ch[c]) u = u -> ch[c];
		else{
			u -> ch[c] = new Node;
			u = u -> ch[c];
		}
	}
	u -> cnt ++ ;
}
int query(string s){
	auto u = root;
	for (auto c : s){
		if (!u -> ch[c]) return 0;
		u = u -> ch[c];
	}
	return u -> cnt;
}
void solve(){
	cin >> n >> q;
	root = new Node();
	for (int i = 1; i <= n; i ++ ){
		cin >> s;
		insert(s);
	}
	root -> dfs();
	for (int i = 1; i <= q; i ++ ){
		cin >> s;
		cout << query(s) << "\n";
	}
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	cin >> T;
	while ( T -- )
		solve();
	return 0;
}