我一直在寻找关于后缀树的教程很长一段时间 . 在SO中，我发现了2篇关于理解后缀树的帖子：1，2 .
但我不能说我理解如何 Build 一个，哎呀 . 在Skiena的书“算法设计手册”中，他说：
由于线性时间后缀树构造算法非常重要，我建议使用现有的实现 .
那么，后缀树的在线构造算法是如此难以实现吗？任何人都可以让我朝着正确的方向去理解它吗？
无论如何，切入追逐，除了建设之外，还有一件我对后缀树不了解的事情 . 因为后缀树中的边只是一对整数（右？）指定子串的起始和结束位置，那么如果我想在这个后缀树中搜索字符串 x ，我应该怎么做？在后缀树中取消引用那些整数，然后将它们逐个与 x 进行比较？不可能这样 .
3 回答
首先，有许多方法来构造后缀树 . Weiner（1973）的原始O（n）方法，由McCreight（1976）改进的方法，Ukkonen最着名的方法（1991/1992），以及一些进一步的改进，主要与实施和储存有关效率考虑 . 其中最值得注意的可能是Giegerich和Kurtz的_2526045 .
此外，由于 suffix arrays 的直接构建在2003年的O（n）时间内已经成为可能（例如使用Skew algorithm，但也有其他的），并且因为有充分研究的方法
使用后缀数组模拟后缀树（例如Abouelhoda/Kurtz 2004）
压缩后缀数组（参见调查的Navarro/Mäkinen 2007）
后缀数组通常比后缀树更受欢迎 . 因此，如果您的目的是为特定目的构建高度优化的实现，您可能需要研究后缀数组构造算法 .
但是，如果您对后缀树构造感兴趣，特别是Ukkonen算法，我建议您仔细查看this SO post中已经提到过的描述，并尝试一起改进该描述 . 这肯定远非完全直观的解释 .
To answer the question about how to compare input string to edge labels: 出于效率原因，在构造和查找期间，每个边标签的 initial character 通常存储在节点中 . 但是其余部分必须在主文本字符串中查找，就像你说的那样，这确实会引起问题，特别是当字符串太大而不能容易地保存在内存中时 . （加上事实，就像任何树的直接实现一样，后缀树是一个包含大量指针的数据结构，它消耗大量内存并且难以维护引用的局部性并从内存缓存中受益）后缀树难以处理的主要原因之一是倒排索引 .
如果你将后缀数组与 lcp table 和 child table 结合起来，当然你应该这样做，你基本上得到一个后缀树 . 这一点在文章中提出：Kim，Park和Kim的Linearized Suffix Trees . lcp表启用了一个相当笨拙的自下而上遍历，子表可以轻松遍历任何一种类型 . 所以关于后缀树的故事使用引起参考问题局部性的指针在我看来是过时的信息 . 因此，只要使用底层后缀数组实现树，后缀树就是“正确而简单的方法” .
Kim，Park和Kim的论文描述了Abouelhoda等人误导性 Headers 文章中的方法变体：用后缀阵列替换后缀树 . Kim等人的文章认为这是一个 implementation 的后缀树，而不是 replacement . 此外，在Kim等人的文章中更详细和直观地描述了Abouelhoda等人的构造的细节 .
，
那里有's an implementation of Ukkonen' s后缀树的线性构造（加上后缀数组，lcp数组）：http://code.google.com/p/text-indexing/ . 与suffixtree.js一起提供的可视化可能会有所帮助