字符串后缀树的隐式表示

Question

从数据结构与算法分析Java中，魏斯匹配：

维斯写道：

1. 在树叶中，我们使用后缀开始的索引（如在后缀数组中）
2. 在内部节点中，我们存储从根开始匹配的常用字符数，直到内部节点;这个数字代表字母深度。

我的问题：给定的输入字符串（例如“香蕉”）和后缀树的隐式表示，将好的算法用于字符串搜索是什么样子？我见过的算法假定树的不同表示。我想做子串搜索而不转换成不同的树形表示。

Answer 1

我从来没有见过这种表现形式。将边上的标签表示为从原始字符串中勾勒出一系列字符的整数对更为常见，这可以让您更轻松地确定边缘上的字符（您可以回头看看原始字符串字符在需要的基础上，以查看它们是否与您正在查看的子字符串匹配）。

我相当肯定，这种压缩表示不匹配子字符串。为了追随边缘，你需要知道边缘上的字符是什么，但是除非你扫描原始字符串的字符以找到可能匹配的东西，否则你不能分辨这些字符是什么。您可以考虑降序到子树中以找到后缀并使用它来重构字符，但这需要额外的时间并打破您期望后缀树的时间范围。

我最好在这里猜测，作者误解了如何在少量空间中表示后缀树。