有时候我们要维护一个字符串集合，然后支持插入、删除、查询某个字符串出现次数和查询某个字符串作为前缀的出现次数。
显然的，暴力肯定 T 飞。
hash：我来！（非常好数据，使我的 hash WA）
所以我们需要字典树。
字典树有三大两大优点：
-
速度快
-
无失误（hash 有一定概率会冲突）
-
支持多模式串匹配
但是，字典树的内存特别庞大，所以数据规模庞大的时候还是乖乖用 hash 吧。
不过，字典树似乎不支持快速判断区间回文串（hash + 树状数组可以 \(O(\log N)\) 完成）。
字典树的结构
下图是一个由 \(\{ \text{a}, \text{asf}, \text{e}, \text{eryt}, \text{radix}, \text{sda} \}\) 构成的 Trie：
（使用 usfca 制作，具体链接可以在 OI-wiki 找到）
可以看到，字典树是一个有向树。
理解（初学者不建议打开）
至于为什么，首先需要理解自动机的概念。自动机用于判断一组信号序列是否合法（很像图灵机是不是）。
以下是一个判断某个数是否是偶数（以二进制输入）的自动机：
而 Trie 树，就是在给定一个字符串后，如果这个字符串是字符串集合的一个串，那么就接受（上面的“查询某个字符串出现次数和查询某个字符串作为前缀的出现次数”需要两个 Trie，但是可以压成一个）
字典树的操作
插入
很简单，遇到不存在的节点创造一个。
记得维护信息。
删除
遇到一个再也不用的节点就删掉。
记得维护信息。
查找某个字符串
一个一个字符的跳。
查找某个前缀
一样一个一个字符的跳，跳完后返回子树和。
标签：hash,一个,text,某个,字符串,字典 From： https://www.cnblogs.com/hhc0001deljbk/p/18110341