后缀树和尝试。 有什么不同?

我正在阅读关于前缀树和Suffix Trees Tries
虽然我已经find了Trie代码,但我找不到Suffix Tree的示例。 另外我感觉到构buildTrie的代码和Suffix Tree的代码是一样的,唯一不同的是,在前一种情况下,我们存储前缀,但在后面的后缀中。
这是真的? 任何人都可以帮我在我的脑海中清除这个问题吗? 一个示例代码将是很大的帮助!

后缀树可以被视为一个build立在trie之上的数据结构,而不是仅仅把string本身添加到trie中,而是添加该string的每个可能的后缀。 举个例子,如果你想在后缀树中索引string香蕉 ,你可以使用下面的string构build一个trie:

 banana anana nana ana na a 

一旦完成,您可以search任何n-gram,并查看它是否存在于索引string中。 换句话说,n-gramsearch是对string所有可能后缀的前缀search。

这是构build后缀树最简单和最慢的方法。 事实certificate,这个数据结构上有许多更好的变体,可以改善空间和构build时间。 在这个领域,我还不够精通,但是你可以从后面的数组或者这个高级的数据结构 (第16和18章)开始。

这个答案也是一个奇妙的工作,解释了这个数据结构的一个变种。

如果你想象一个Trie,你在其中放置了一些单词的后缀,你可以很容易地查询它的string的子串。 这是后缀树的主要思想,它基本上是一个“后缀树”。

但是使用这种天真的方法,构造一棵长度为n的string的树将会是O(n ^ 2)并占用大量的内存。

由于这个树的所有条目都是相同string的后缀,所以它们共享很多信息,所以有优化的algorithm可以让你更高效地创build它们。 例如,Ukkonen的algorithm允许您以O(n)时间复杂度在线创build后缀树。

差别很简单。 后缀树比后缀trie具有更less的“虚拟”节点。 这些虚拟节点是单个字符,用于增加树中的查找操作