algorithm - Suffix tree VS Tries - 简单的英语，有什么区别？

Question

我已经查看了这个问题，但我仍然看不出 Suffix tree 和 Trie 之间的区别。

两者都有给定字符串的所有子字符串，那么它们之间有什么不同呢？

Answer 1

后缀树 - 给出一个大文本。查询 - 多次搜索文本中的任何单词。
示例：您正在使用纸牌和小猫实现自己的酷文本编辑器=）您将实现CTRL+F功能。可能的实现 - 索引文档（创建后缀树）并且当用户查找某个单词时 - 在树中搜索它。

Trie - 给出一个大文本。查询 -在文本中多次搜索预定义的单词。
示例：您正在使用扑克和 Justin Bieber 的粉丝实现您自己的酷 Facebook=) 您不希望您的用户发布脏话。可能的实施 - 创建脏话的特里。当用户键入一些文本时，搜索禁止使用的单词并将其替换为 *。

一般来说，后缀树=特里。后缀树是某个单词的所有后缀的 trie。当您想在字典中搜索某些内容时，请使用 trie。当您在纯文本中搜索某些内容时，请使用后缀树。

重要提示 - 为大文本构建/重建后缀树是复杂的操作。更改文本后，您必须重新创建后缀树。重建 trie 是一项微不足道的操作 - 只需在其中添加新单词O(wordLength)

结论
后缀树。您对未来的查询一无所知。花时间创建后缀树，您就可以处理请求了。已知信息是文本。请求未知但给出文本且不会经常更改的情况是使用后缀树的候选者。例如，您不能在CTRL+F实现中使用 trie（aho-corasick 算法） - 因为您不能将字典作为基于 trie 的 aho-corasick 算法的输入。

特里。您对将执行搜索的文本一无所知。 但你知道未来的查询。花时间为您的查询预处理/准备数据结构，您可以在任何文本中执行搜索查询。例如，在替换禁用词任务中，您不知道用户将发布什么文本，但您知道禁用词。为每个简短的新帖子创建后缀树太愚蠢了=) UPD正如@mightyWOZ 在评论中注意到的那样，纯 trie 不适用，但我们可以使用 Aho-Corasick 算法，它是 trie 的扩展。因此，对于尝试而言，声明仍然是正确的 - 存在使用 trie 作为基础的方法 (Aho-Corasick)，预处理查询，然后可以处理任何文本。