后缀树

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

后缀树空间压缩

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

后缀树的构造

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

请我喝[茶]~( ̄▽ ̄)~*

fightinggg 微信支付

微信支付

fightinggg 支付宝

支付宝

fightinggg 贝宝

贝宝