Trie 字典树

构造

trie 上的每个节点表示一个字符，而 trie 的根到 trie 上某个节点的路径即代表了一个字符串。实现较为简单，每个节点记录字符集大小个儿子的 \(\text{idx}\) 即可。

例题

UVA1401 Remember the Word

给出⼀个由 \(S\) 个不同单词组成的字典和⼀个长字符串。把这个字符串分解成若⼲个单词的连接（单词可以重复使⽤），有多少种⽅法？

待分解字符串⻓度不超过 \(300000\)，单词个数不超过 \(4000\)，每个单词⻓度不超过 \(100\)。

sol：不难考虑到 dp。令 \(f_i\) 表示 \([i,n]\) 的字符串划分方案数。那么 \(f_i=\sum f_{i+x}[s_{[i,i+x-1]}\in S]\)。在 trie 树上查找即可。由于 trie 的深度 \(\le 100\)，故复杂度 \(O(100n)\)。

01Trie

构造

显然，就是字符集为 \(\{0,1\}\) 的 trie 树，通常用于解决各种二进制位运算求 最大/最小 值的问题。较为简单，不再赘述。

例题

AcWing143 最大异或对

在给定的 \(N\) 个整数 \(A_1,A_2\dots A_N\) 中选出两个进行 \(\text{xor}\) 运算，得到的结果最大是多少？\(1\le N\le 10^5,0\le A_i<2^{31}\)。

Sol：01Trie 模板题。从前往后一次插入 \(N\) 个数，枚举到第 \(i\) 个数是，先查询 01Tire 上与 \(A_i\) 的 \(\text{xor}\) 最大的是多少，每次尽可能与 \(A_i\) 这一位走不同方向。查询完后插入即可。复杂度 \(O(n\log V)\)。