Trie字典树
小柯
2020-02-04 22:25:53
# 定义
在计算机科学中，Trie，又称前缀树或字典树，是一种有序树状的数据结构，用于保存关联数组，其中的键通常是字符串。
# 例子
一棵正确的Trie树像下面一样：
但是注意！！！
字符数据体现在Trie的边上，而节点本身只需要存储自己是否是一个字符串的结尾即可。
# Update 8.7
对于“字符数据体现在Trie的边上，而节点本身只需要存储自己是否是一个字符串的结尾即可。”可以从存储方式来体现。
一般我们都是维护一个数组 $t[u][c]$ 表示 $u$ 节点以字符 $c$ 连接的儿子的编号，然后维护另一个数组 $cnt[u]$ 表示 $u$ 节点是多少个字符串的结尾(如果字符串有重复)。
# 补：应用之后缀树
>后缀Trie，故名思义，就是将一个字符串所有的后缀都插入Trie中。
>压缩Trie，除根节点外没有度为二的节点的Trie。（压缩Trie的边可能是字符串）
将Trie转为压缩Trie的方法：不断地将只有一个儿子的节点向父亲合并，并将这个节点到儿子的字符(串)，添加到父亲到这个节点的字符(串)后面。
>后缀树，即压缩后缀Trie。
### 应用：模式匹配
> 构造主串的后缀树，并用模式串在后缀树上匹配。
原理：若模式串是主串的子串，那么它一定是主串某个后缀的前缀。
### Ukkonen线性构造算法
(这坑以后再填吧，也当是复习...)