Solves

Appearance

Trie(字典树) ​

概念 ​

Trie 树又叫前缀树、字典树、单词查找树或者是键树，是一种多叉树结构。

trie树

边代表字母：

Trie

实现 ​

维护一个字符串集合，支持两种操作：

  1. I x 向集合中插入一个字符串 x；
  2. Q x 询问一个字符串在集合中出现了多少次。

共有 N 个操作，所有输入的字符串总长度不超过 107，字符串仅包含小写英文字母。

# 输入
5
I abc
Q abc
Q ab
I ab
Q ab

# 输出
1
0
1

参考代码：

cpp
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int trie[N][26], cnt[N], idx; // 下标为0的结点，既是根节点又是空结点

void insert(char str[]) {
    int p = 0;
    for (int i = 0; str[i]; i++) {
        int u = str[i] - 'a';
        if (!trie[p][u]) trie[p][u] = ++idx;
        p = trie[p][u];
    }

    cnt[p]++;
}

int query(char str[]) {
    int p = 0;
    for (int i = 0; str[i]; i++) {
        int u = str[i] - 'a';
        if (!trie[p][u]) return 0;
        p = trie[p][u];
    }

    return cnt[p];
}

int main() {
    int n; cin >> n;
    while (n--) {
        char op[2], str[N];
        scanf("%s %s", op, str);
        if (op[0] == 'I') insert(str);
        else cout << query(str) << endl;
    }

    return 0;
}

// 使用其他数据结构可以做吗？当然可以的，对于这道题我们可以使用C++中的STL中的map
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;

int main() {
    int n; cin >> n;
    map<string, int> h;

    while (n--) {
        string op, str;
        cin >> op >> str;

        if (op[0] == 'I') h[str]++;
        else cout << h[str] << endl;
    }

    return 0;
}

习题 ​

洛谷 P2580. 于是他错误的点名开始了 ​

  • Trie 检索字符串
cpp
#include <iostream>
#include <cstdio>
using namespace std;

const int N = 1e6 + 10;
int trie[N][26], idx = 1, n, m, tag[N];

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		string s; cin >> s;
		int u = 1;
		for (int j = 0; j < s.size(); j++) {
			if (!trie[u][s[j] - 'a']) {
				trie[u][s[j] - 'a'] = ++idx;
			}
			u = trie[u][s[j] - 'a'];
		}
		tag[u] = 1;
	}

	cin >> m;
	while (m --) {
		string s; cin >> s;
		int u = 1;
		for (int i = 0; i < s.size(); i++) {
			u = trie[u][s[i] - 'a'];
			if (!u) break;
		}

		if (tag[u] == 1) {
			tag[u] = 2;
			puts("OK");
		} else if (tag[u] == 2) {
			puts("REPEAT");
		} else {
			puts("WRONG");
		}
	}

	return 0;
}

洛谷 P8306. 字典树 ​

cpp
#include <bits/stdc++.h>
using namespace std;

const int N = 3e6 + 10;

int trie[N][65], cnt[N], idx;

char str[N];
int n, q;

int mapping(char c) {
	int u;
	if (c >= '0' && c <= '9') {
		u = c - '0' + 52;
	} else if (c >= 'A' && c <= 'Z') {
		u = c - 'A' + 26;
	} else {
		u = c - 'a';
	}

	return u;
}

void insert(char str[]) {
	int p = 0;
	for (int i = 0; str[i]; i++) {
		int u = mapping(str[i]);

		if (!trie[p][u]) trie[p][u] = ++idx;
		p = trie[p][u];
		cnt[p]++;
	}
}

int query(char str[]) {
	int p = 0;
	for (int i = 0; str[i]; i++) {
		int u = mapping(str[i]);

		if (!trie[p][u]) return 0;
		p = trie[p][u];
	}

	return cnt[p];
}

int main() {
	int t; scanf("%d", &t);

	while (t--) {
		memset(trie, 0, sizeof trie);
		memset(cnt, 0, sizeof cnt);
		idx = 0;

		scanf("%d%d", &n, &q);

		while (n--) {
			scanf("%s", str);
			insert(str);
		}
		while (q--) {
			scanf("%s", str);
			printf("%d\n", query(str));
		}
	}

	return 0;
}

洛谷 P4551 最长异或路径 ​

分析：任选一点作为根 root，设 T(u,v) 表示 u 和 v 之间的路径边权异或之和，有 T(u,v)=T(root,u)⊕T(root,v) 因为 a⊕a=0,0⊕x=x。此时考虑将所有的 T(root,u) 插入到 Trie 树中，就可以求出与它异或和最大的 T(root,v)。从 Trie 根开始，每一位选择与 T(root,u) 当前位不同的子树走，否则没有选择。因为 1⊕1=0,1⊕0=1。

cpp
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10, M = N * 2;
int h[N], e[M], w[M], ne[N], idx;
int dis[N];
int trie[N * 32][2], tot;
int ans, n;

void add(int a, int b, int c) {
	e[idx] = b;
	w[idx] = c;
	ne[idx] = h[a];
	h[a] = idx++;
}

void insert(int x) {
	int p = 0;
	for (int i = 30; i >= 0; i--) {
		int t = (x >> i) & 1;
		if (!trie[p][t]) trie[p][t] = ++tot;
		p = trie[p][t];
	}
}

void query(int x) {
	int res = 0, p = 0;
	for (int i = 30; i >= 0; i--) {
		int t = (x >> i) & 1;
		if (trie[p][t ^ 1]) {
			p = trie[p][t ^ 1];
			res |= (1 << i);
		} else {
			p = trie[p][t];
		}
	}

	ans = max(ans, res);
}

void dfs(int u, int fa) {
	insert(dis[u]);
	query(dis[u]);
	for (int i = h[u]; i != -1; i = ne[i]) {
		int j = e[i];
		if (j == fa) continue;
		dis[j] = dis[u] ^ w[i];
		dfs(j, u);
	}
}

int main() {
	memset(h, -1, sizeof h);
	cin >> n;
	for (int i = 1; i < n; i++) {
		int a, b, c; cin >> a >> b >> c;
		add(a, b, c); add(b, a, c);
	}

	dfs(1, 0);

	cout << ans << endl;

    return 0;
}

Copyright © 2025-present loop3r