string - 什么是广义后缀树？

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 ₂的所有后缀，但它还将包含许多从 T ₁开始并传播到 T ₂的“虚假”后缀。为了解决这个问题，在构建初始后缀树之后，您通常会在树结构上进行第二次遍历，并消除任何超出 $ ₁标记的后缀。这就是为什么，例如，您在上面给出的广义后缀树不包含 ABAB$ ₁ BABA$ ₂。

至于你的下一个问题——叶子上的数字是多少？- 后缀树中的每个叶子通常都用叶子对应的后缀的起始索引进行标记。在广义的后缀树中，每个叶子都被标记了两条信息——后缀的起始索引，以及后缀属于哪个字符串。叶子上的符号 a:b 表示“这个后缀来自字符串 a，它从该字符串中的索引 b 开始。” 例如，最左边叶子上的标记 1:3 表示“这个后缀来自字符串 1，它从位置 3 开始”。您可以看到这对应于后缀 A$ ₁，假设 1 索引，它确实从 ABAB$ 1 中的位置 3 开始_。

希望这可以帮助！