博客

后缀树，就是把

一串字符

的

所有后缀

保存并且压缩的字典树。相对于字典树来说，后缀树

并不是针对大量字符串的，而是针对一个或几个字符串来解决问题

。比如字符串的回文子串，两个字符串的最长公共子串等等，后面应用会说。

一、建立后缀树

比如单词banana，它的所有后缀显示到下面的。1代表从第一个字符为起点，终点不用说都是字符串的末尾。

以上面的后缀，我们建立一颗后缀树。如下图，为了方便看到后缀，我没有合并相同的前缀。

后缀树是把一个字符串所有后缀压缩并保存的字典树，所以我们把字符串的所有后缀还是按照字典树的规则建立，就成了上图的样子。 注意还是和字典树一样，根节点必须为空。

二、压缩后缀树

下面说下更加节省空间的方案，也就是上面提到的压缩。