Trie树 | 学习笔记

$\rm Trie$ 树 (字典树)

高效存储和查找字符串集合

在很多处理字符串前缀的题中有奇妙作用.

图解：

前置数组：

int son[N][26]; // 每个节点连到的子节点
int idx; // 当前用到了哪些下标, 根节点 root 和空节点都指向 0
int cnt[N]; // 以当前点结尾的字符串有多少个
char str[N];

插入：

void insert(char str[]) {
	int p = 0; // 从根节点 0 开始遍历 
	for (int i = 0; str[i]; i ++) {
		int u = str[i] - 'a'; // 映射字母以查找或添加子节点
		if (!son[p][u]) son[p][u] = ++ idx; // 如果没有此字母的子节点, 那么创建一个
		p = son[p][u]; // 向下走一个点 
	}
	// 此时将待插入的字符串全部遍历完毕 
	cnt[p] ++; // 标记结尾节点, 以此节点结束的字符串多了一个 
}

查找：

int query(char str[]) {
// 返回字符串出现多少次
	int p = 0;
	for (int i = 0, u; str[i]; i ++) {
		u = str[i] - 'a';
		if (!son[p][u]) return 0; // 如果不存在此字母的子节点, 那么直接 
		p = son[p][u]; // 如果存在当前子节点, 走向那个 
	}
	// 此时将带查找的字符串遍历完毕 
	return cnt[p];
}

应用: THUSC2016 补退选

练手题, 很简单, 自己想咯.

扩展: $\rm Trie$ 树上 $\rm dp$

Remember the Word

不难想到一个朴素的 $\rm dp$ 方式:

设 $dp_i$ 表示匹配长串 $1 \sim i$ 的方案.

每次拿一个串去尝试匹配, 利用哈希可以做到 $O(n \cdot m)$.

但发现短串长度不超过 100, 因此可以将所有短串插入 $\text{Trie}$ 树, 将原串的后缀在 $\text{Trie}$ 树上跑, 遇到结尾标记则代表完全覆盖了一个子串, 以此更新 dp 值, 由于短串长度不超过 $100$, 因此每次更新范围最多为 $100$, 时间复杂度 $O(100 \cdot n)$.

一个优化是: 将 $\rm dp$ 状态改设为匹配一段后缀, 每次更新时将从 $i$ 开始的后缀在 $Trie$ 树上跑, 这样字符串的起点确定, 方便更新.

int n, dp[L], cnt;
string s, a;
int tr[M][30], idx;
bool st[M];

inline void upd(int &x, int y) { x += y; (x >= MOD) and (x -= MOD); }
int main() {
	cin >> s >> n;
	for (int i = 1; i <= n; ++ i) cin >> a, insert(a);
	dp[s.size()] = 1;
	for (int i = s.size() - 1; ~i; -- i) {
		int p = 0;
		for (int j = i; j < s.size(); ++ j) {
			if (!tr[p][s[j] - 'a']) break; // 不存在该节点直接退出即可. 
			p = tr[p][s[j] - 'a']; 
			if (st[p]) upd(dp[i], dp[j + 1]);
		} 
	}
	cout << dp[0] << '\n';
}

Representative Sampling

简化题意:

给定 $n$ 个字符串 $a_1, a_2, \cdots, a_n$, 从中选 $k$ 个, 求它们两两之间的最长公共前缀之和的最大值.

$k \leqslant n \leqslant 2000, |a_i| \leqslant 500$.

$Solutions$

从一个集合中选出一个子集, 使得某某式子最大这类问题, 除了枚举子集的暴力, 大概只能考虑 $\rm dp$.

考虑在 $\rm Trie$ 树上进行树形 $\rm dp$, 设 $f_{u, j}$ 表示在以 $u$ 节点为根的子树中选择了 $j$ 个结束节点两两之间最长公共前缀之和的最大值, 转移类似于树形背包. 为了不重复计算贡献, 每次只加上从 $u$ 向 $fa_u$ 贡献的权值即可.

$$f_{u, j} = \max_{v \in son(u)} f_{v, k} + f_{u, j - k} + \frac{j \times (j - 1)}{2}$$

这样 $\rm dp$ 的复杂度是 $O(\sum\limits_{i = 1}^{n} a_i \times k)$.

但我们发现, 我们可以一次性处理一条链上的转移, 只需要将 $frac{j \times (j - 1)}{2}$ 这一项乘上所有边权即可, 因此可以在 $\rm Trie$ 树上建虚树, 将结束节点和结束节点的 $\rm lca$ 保留转移即可, 这样节点的规模是 $O(n)$ 的, 复杂度 $O(nk)$, 可以通过.

---

$\text{0-1 Trie}$

基本思想

将数字转化为二进制串储存, 成为树结构

void insert(int u) {
	int p = 0; // 根结点指针
	for (int i = 20; i >= 0; i --) {
		int c = (u >> i) & 1;
		if (!son[p][c]) son[p][c] ++ idx;
		p = son[p][c];
	}
}

应用: 不知道哪看的题

简化题意

给定两个数组 $\rm {A }, {B }$, 定义 $\rm C_i = A_i\ xor\ B_i$. 要求重排两个序列使得 $\rm {C }$ 的字典序最小. $n \leqslant 10^5, a_i, b_i \leqslant 2^{30}$.

$Solutions$

考虑合并 $\rm A, B$ 集合的 $\rm Trie$ 树. 同时递归遍历两棵 $\rm Trie$, 优先将同字符(‘00’, ‘11’) 合并, 剩下的部分互相合并即可.