algorithm - 后缀树 VS 尝试 - 用简单的英语来说，有什么区别？

Question

我看过this问题，但我仍然看不出后缀树和 Trie 之间的区别。

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

Answer 1

后缀树 - 给出了大文本。查询 - 多次搜索文本中的任何词。
例子:您正在使用纸牌和小猫实现您自己的超酷文本编辑器=) 您将要实现 CTRL+F 功能。可能的实现 - 索引文档(创建后缀树)，当用户查找某个词时 - 在树中搜索它。

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

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

重要说明 - 为大文本构建/重建后缀树是一项复杂的操作。更改文本后，您必须重新创建后缀树。重建 trie 是一个微不足道的操作 - 只需在 O(wordLength)

中添加新单词

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

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