根据Java中的数据结构和算法分析，Weiss：
魏斯写道：
在叶子中，我们使用后缀开始的索引（如后缀数组中）在内部节点中，我们存储从根到内部节点匹配的公共字符数;这个数字代表字母深度 .
我的问题：给定输入字符串（例如'banana'）和后缀树的隐式表示，子字符串搜索的好算法是什么样的？我见过的算法假定树的不同表示 . 我想做子字符串搜索而不转换为不同的树表示 .
我以前从未见过这种表现形式 . 更常见的是将边缘上的标签表示为原始字符串中描述一系列字符的整数对，这样可以更轻松地确定边缘上的字符是什么（您可以回顾那些字符串处的原始字符串）根据需要使用字符来查看它们是否与您正在查看的子字符串匹配） .
我很确定这种压缩表示不适合匹配子串 . 为了跟踪边缘，您需要知道该边缘上的字符是什么，但除非您扫描原始字符串的字符以找到可以想象匹配的字符，否则您无法分辨这些字符是什么 . 您可以考虑下降到子树中以在那里找到后缀并使用它来重建字符，但这需要额外的时间并打破您对后缀树所期望的时间限制 .
我最好的猜测是作者错误地认为如何在少量空间中表示后缀树 .
1 回答
我以前从未见过这种表现形式 . 更常见的是将边缘上的标签表示为原始字符串中描述一系列字符的整数对，这样可以更轻松地确定边缘上的字符是什么（您可以回顾那些字符串处的原始字符串）根据需要使用字符来查看它们是否与您正在查看的子字符串匹配） .
我很确定这种压缩表示不适合匹配子串 . 为了跟踪边缘，您需要知道该边缘上的字符是什么，但除非您扫描原始字符串的字符以找到可以想象匹配的字符，否则您无法分辨这些字符是什么 . 您可以考虑下降到子树中以在那里找到后缀并使用它来重建字符，但这需要额外的时间并打破您对后缀树所期望的时间限制 .
我最好的猜测是作者错误地认为如何在少量空间中表示后缀树 .