Trie字典树

· · 个人记录

定义

在计算机科学中，Trie，又称前缀树或字典树，是一种有序树状的数据结构，用于保存关联数组，其中的键通常是字符串。

例子

一棵正确的Trie树像下面一样：

但是注意！！！

字符数据体现在Trie的边上，而节点本身只需要存储自己是否是一个字符串的结尾即可。

Update 8.7

对于“字符数据体现在Trie的边上，而节点本身只需要存储自己是否是一个字符串的结尾即可。”可以从存储方式来体现。

一般我们都是维护一个数组 t[u][c] 表示 u 节点以字符 c 连接的儿子的编号，然后维护另一个数组 cnt[u] 表示 u 节点是多少个字符串的结尾(如果字符串有重复)。

补：应用之后缀树

后缀Trie，故名思义，就是将一个字符串所有的后缀都插入Trie中。

压缩Trie，除根节点外没有度为二的节点的Trie。（压缩Trie的边可能是字符串）

将Trie转为压缩Trie的方法：不断地将只有一个儿子的节点向父亲合并，并将这个节点到儿子的字符(串)，添加到父亲到这个节点的字符(串)后面。

后缀树，即压缩后缀Trie。

应用：模式匹配

构造主串的后缀树，并用模式串在后缀树上匹配。

原理：若模式串是主串的子串，那么它一定是主串某个后缀的前缀。

Ukkonen线性构造算法

(这坑以后再填吧，也当是复习...)