后缀阵列与后缀树

Question

我只想知道,当后缀树优于增强后缀数组时.

在阅读了使用增强的suf fi x数组替换suf fi x树之后,我再也看不到使用后缀树的理由了.有些方法可能会变得复杂,但您可以使用后缀数组执行所有操作,使用后缀树可以执行的操作,并且需要相同的时间复杂度但内存较少.

一项调查甚至表明,后缀数组更快,因为它们缓存更友好,并且不会产生更多的缓存未命中,然后产生后缀树(因此缓存可以更好地预测数组使用,然后在递归树结构上).

那么,有没有人知道在后缀数组上选择后缀树的原因？

编辑好的,如果你知道更多告诉我,到目前为止:

Answer 1

SO 本身对这个主题有一些有趣的想法。您还可以在线找到更多可用的技术材料。还有另一篇论文可能会帮助您解决问题，声称这是实现这些结构的另一种有效方法。

我不是这个问题的专家，但在我看来，后缀数组可能会慢一些，尽管它们更节省空间。然而，我缺乏实践经验来更详细地了解它们。