后缀树如何工作？

Question

我正在阅读"算法设计手册"中的数据结构章节,并遇到了后缀树.

该示例说明:

输入:

XYZXYZ$
 YZXYZ$
  ZXYZ$
   XYZ$
    YZ$
     Z$
      $

输出:

我无法理解从给定的输入字符串生成该树的方式.后缀树用于在给定的字符串中查找给定的子字符串,但给定的树如何帮助它呢？我确实理解下面显示的另一个trie示例,但如果下面的trie被压缩到后缀树,那么它会是什么样子？

Answer 1

用于构造后缀树的标准有效算法肯定是非常重要的.这样做的主要算法称为Ukkonen算法,并且是对两个额外优化的朴素算法的修改.您可能最好阅读此前面的问题,了解有关如何构建它的详细信息.

您可以通过在基数尝试上使用标准插入算法来构造后缀树,以将每个后缀插入树中,但这样做需要花费时间O(n ²),这对于大字符串来说可能是昂贵的.

至于快速子字符串搜索,请记住后缀树是原始字符串的所有后缀的压缩trie(加上一些特殊的字符串结尾标记).如果字符串S是初始字符串T的子字符串,并且您拥有T的所有后缀的trie,那么您可以只搜索以查看T是否是该trie中任何字符串的前缀.如果是这样,则T必须是S的子字符串,因为它的所有字符都存在于T中的某个位置.后缀树子字符串搜索算法正是这种搜索应用于压缩的trie,在每个步骤中都遵循相应的边.

希望这可以帮助!