suffix-tree - 为什么这个字符串的后缀树中这两个节点之间没有后缀链接？
问题描述
我正在学习如何从给定字符串生成后缀树的 Ukkonen 算法。我在可视化网站http://brenden.github.io/ukkonen-animation/中尝试了一个字符串“dedododeodo”，我不完全理解的一件事是：为什么从节点号 8 到节点号 3 没有任何后缀链接?
我的理解是：路径标签是“od”，那么它应该链接到另一个节点“d”。这里的节点 8 和节点 3 都是内部节点。我不明白为什么从节点 8 到节点 3 没有后缀链接。
我知道后缀链接是在相内而不是相间生成的。但是如果你走到第 21 步的第 17 步，那么你很快就会看到和我一样的困惑。在字符'$'的规则2扩展之后，我们应该遵循节点8的后缀链接，它根本不存在（或者你可以说指向root）。
可视化网站选择在节点3之后跳转到边缘。
我在这里错过了什么吗？我从这个链接中学到了一篇文章Ukkonen's suffix tree algorithm通俗的英文，有时后缀链接不存在，所以我们必须从树的根部重新扫描。
如果作者说的是真的，那么它是如何影响运行时复杂度的呢？我的意思是，Ukkonen 算法的整个思想是基于几个重要的技巧，其中之一就是后缀链接，对吧？
我读过一些关于线性时间复杂度证明的文章。后缀链接对于保证线性复杂度非常重要。使用后缀链接，节点深度最多下降2，树深度最多为n。有了这两个约束，我们可以说后缀树中“down-walk”的数量是有上限的。通过重新扫描，线性时间复杂度将不再成立？
请帮忙。谢谢。我的实现 C++ 源代码在这里：https ://github.com/hdc1112/SuffixTree
解决方案
我刚刚又读了一遍 Gusfield G 的书，并截取了一个重要定理的截图。定理告诉我们，后缀链接可以有两种情况：一是从之前创建的内部节点到新创建的内部节点；第二，它是从一个内部节点到另一个已经存在的内部节点。
该定理告诉我们，后缀链接结束节点既可以创建也可以找到。