是的我读过这个：Ukkonen's suffix tree algorithm in plain English?
这是对算法的一个很好的解释，但它不是杀死我的算法本身，而是用于实现它的数据结构 .
我需要尽可能最小和尽可能快的数据结构，我已经看到许多实现仅使用节点，一些只有边缘，一些有边缘和节点等 . 然后有变化，我正在阅读的网站声称一个节点不需要指向其父节点，其他地方不会考虑节点的子节点的管理方式 .
我的想法是使用int start和int * end（指向当前结束或阶段i）的Node结构 . 每个节点都有一个suffix_link指针，一个指向其父节点的指针，以及一个指向包含其子节点的向量的指针 .
我的问题是，这些东西是否足以实现后缀树？我能以任何方式最小化它吗？我还没有看到有关载体中的孩子的实现，所以我对自己的想法持怀疑态度 . 有人可以解释一下只使用节点以这种方式实现后缀树需要什么？
2 回答
当我必须实现该算法时，更好的解释文档是原始Ukkonen paper并且有一个newer with images .
在这些文件中是的，所有内部都实现了Ukkonen的后缀树算法 .
以下可能会有所帮助：
Ukkonen’s Suffix Tree Construction
我们在这里
1.开始，结束表示边缘标签
2.后缀链接
3.儿童阵列