algorithm - 与后缀树的隐式表示匹配的字符串

Question

来自 Java 中的数据结构和算法分析，Weiss:

魏斯写道:

1. In the leaves, we use the index where the suffix begins (as in the suffix array)
2. In the internal nodes, we store the number of common characters matched from the root until the internal node; this number represents the letter depth.

我的问题:给定输入字符串(例如“banana”)和后缀树的隐式表示，一个好的子字符串搜索算法应该是什么样的？我见过的算法假设树的不同表示。我想在不转换为不同的树表示的情况下进行子字符串搜索。

Answer 1

我以前从未见过这种表现形式。更常见的是将边缘上的标签表示为整数对，从原始字符串中划出一定范围的字符，这样您就可以更轻松地确定边缘上的字符是什么(您可以在那些位置回头看看原始字符串字符，以查看它们是否与您正在查看的子字符串匹配)。

我相当确定这种压缩表示不擅长匹配子字符串。为了沿着一条边，您需要知道该边上有哪些字符，但您无法分辨这些字符是什么，除非您扫描原始字符串的字符以找到可能匹配的字符。您可以考虑向下进入子树以在其中找到一个后缀并使用它来重建字符，但这需要额外的时间并且打破了您对后缀树的时间限制。

我最好的猜测是作者错误地理解了如何在少量空间中表示后缀树。