什么是通用后缀树？

Question

我看到了维基百科页面,但仍然不清楚这个想法.

为了找到2个字符串(T和S)中最长的公共子字符串,我读过我们必须为字符串构建一个后缀树T($1)S($2),其中`($ 1)和($ 2)是不属于字符串的特殊字符.

但对于字符串维基百科的图像ABAB和BABA看起来是这样的:

为什么它不包含整个字符串ABAB($1)BABA($2)？它不是连接字符串的后缀吗？

叶子上的数字是多少？

Answer 1

广义后缀树是后缀树的变体,其中存储了两个(或更多个)不同字符串T ₁和T ₂的后缀,而不仅仅是一个字符串T的后缀.

构建通用后缀树的一种方法是首先为T ₁ $ ₁ T ₂ $ ₂创建一个后缀树.这个结果后缀树将包含T ₁和T _2的所有后缀,但它也将包含很多"假"后缀,这些后缀从T ₁开始并扩展到T ₂.要解决这个问题,在构建初始后缀树之后,通常会对树结构进行第二次传递,并消除延伸超过$ ₁标记的任何后缀.这就是为什么,例如,上面给出的广义后缀树不包含ABAB $ ₁ BABA $ ₂.

至于你的下一个问题 - 树叶中的数字是多少？ - 后缀树中的每个叶子通常用叶子对应的后缀的起始索引标记.在通用后缀树中,每个叶子都标记有两条信息 - 后缀的起始索引和后缀所属的字符串.叶子上的符号a:b表示"此后缀来自字符串a,它从该字符串中的索引b开始." 例如,最左边叶子上的标记1:3表示"此后缀来自字符串1,它从位置3开始".您可以看到这对应于后缀A $ ₁,它确实从ABAB $ ₁中的第3位开始,假设为1-indexing.

希望这可以帮助!