后缀树

后缀树

一颗后缀树是针对一个字符串而言的,该后缀树能识别这个字符串的所有后缀,能且仅能识别这个字符串的所有字串,

后缀树空间压缩

常常我们会在后缀树的边上储存字符串,而不是字符,这样可以避免大量的内存开销,每一条边,我们都记录了两个数据,字符串的起点和终点,这样就实现了后缀树的空间压缩

后缀树的构造

后缀树有很多构造算法,这里直讲最简单的,考虑一个字符串的后缀自动机,其上的paerent树便是反串的后缀树。


后缀树
http://fightinggg.github.io/fluid/Q7A1K1.html
作者
fightinggg
发布于
2020年3月16日
许可协议