广义后缀树是什么？

Question

我看了维基百科的页面，但对这个概念仍不清楚。

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

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

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

那些叶子上的数字是什么意思？

- batman

Answer 1

广义后缀树是后缀树的一种变体，它不仅存储一个字符串T的后缀，还同时存储两个（或多个）不同字符串T₁和T₂的后缀。

构建广义后缀树的一种方法是，首先为T₁$₁T₂$₂制作一个后缀树。这个结果后缀树将包含T₁和T₂的所有后缀，但也会包含很多“虚假”的后缀，这些后缀从T₁开始并传播到T₂。为了解决这个问题，在构建初始后缀树之后，通常需要对树结构进行第二遍扫描，并消除任何超过$₁标记的后缀。例如，您给出的广义后缀树就没有包含ABAB$₁BABA$₂，因为它是一个虚假的后缀。

至于您的下一个问题 - 叶子节点上的数字是什么？- 后缀树中的每个叶子通常都带有后缀的起始索引。在广义后缀树中，每个叶子都标记有两个信息 - 后缀的起始索引以及该后缀属于哪个字符串。叶子上的a:b表示“此后缀来自字符串a，并从该字符串的位置b开始。”例如，在最左边的叶子上的标记1:3表示“此后缀来自字符串1，它在第3个位置开始。”你可以看到这对应于后缀A$₁，假设采用1为起始下标。

希望能帮助到您！

- templatetypedef