澄清关于Ukkonen的后缀树
为了我的工作，我一直在阅读Ukkonen的后缀树，并想确认以下内容是否属实。
在Ukkonen Suffix Tree中说这是否正确：
只有通向叶节点的边可以将多个连续字符压缩为其中的一部分。 内部节点之间的边缘（比如说，从根节点到内部节点）只能表示单个字符。
我不认为这种说法是真实的。 我已经使用这篇文章实现了一个后缀树。 您可以看到他们为示例构建的最终后缀树具有多于一个字母的边缘。
声明是不正确的。 后缀树是帕特里夏树，意思是所有的边都带有字符串标签（任意长度，而不是单个字符）。 但请注意，标签实现为（从，到）对输入文本的引用，因此无论标签的长度如何，边缘占用的内存空间都是O（1）。
链接地址: http://www.djcxy.com/p/40121.html