后缀树 发表于 2020-03-16 分类于 ACM ， 学习笔记 ， 字符串 阅读次数： 本文字数： 298 阅读时长 ≈ 1 分钟 nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 后缀树 一颗后缀树是针对一个字符串而言的，该后缀树能识别这个字符串的所有后缀，能且仅能识别这个字符串的所有字串， # 后缀树空间压缩 常常我们会在后缀树的边上储存字符串，而不是字符，这样可以避免大量的内存开销，每一条边，我们都记录了两个数据，字符串的起点和终点，这样就实现了后缀树的空间压缩 # 后缀树的构造 后缀树有很多构造算法，这里直讲最简单的，考虑一个字符串的后缀自动机，其上的paerent树便是反串的后缀树。