string - 查找与查询 : how to use a suffix tree? 匹配的所有名称

Question

问题:您有一部智能手机并打开了联系人应用程序。您要搜索联系人。让我们说 manmohan。但你不记得他的全名。你只记得 mohan 所以你开始打字。在您键入“m”的那一刻，联系人应用程序将开始搜索具有可用字母“m”的联系人。假设您在联系人列表中存储了姓名 ("manmohan", "manoj", "raghav","dinesh", "aman") 现在联系人将显示 manmohan,manoj 和 aman 结果。现在你输入的下一个字符是'o'(到目前为止你已经输入了“mo”)现在结果应该是“manmohan ”。你会如何实现这样的数据结构？

我的方法是应用 KMP，因为您在所有可用联系人中查找模式“m”然后是“mo”。然后显示匹配的字符串。但是面试官说效率不高。 (我想不出任何更好的方法。)在离开之前，他说有一种算法可以提供帮助。如果你知道它，你可以解决它。我做不到。 (临走前问了一下那个标准算法，面试官说:后缀树)。谁能解释一下怎么更好？或者哪个是实现此数据结构的最佳算法。

Answer 1

您要解决的问题基本上可以归结为以下问题:给定一个固定的字符串集合和一个仅通过追加更改的字符串，您如何有效地找到包含该模式作为子字符串的所有字符串？

关于字符串的一个简洁的小结果通常对处理涉及子字符串搜索的问题很有用:字符串 P 是字符串 T 的子字符串当且仅当 P 是 T 的至少一个后缀的前缀。(做你明白为什么了吗？)

想象一下，您使用词库中的每个名称，并构建一个包含该词库中所有词的所有后缀的 trie。现在，给定要搜索的模式字符串 P，沿着 trie 遍历，读取 P 的字符。如果你从 trie 中掉下来，那么字符串 P 一定不是任何名称库的子字符串(否则，它会是T 中的字符串之一的至少一个后缀的前缀)。否则，你在某个 trie 节点。然后，以您当前正在访问的节点为根的子树中的所有后缀都对应于 T 中所有名称中子字符串的所有匹配项，您可以通过 DFS-ing 子树并记录您找到的所有后缀来找到它们找到。

后缀树本质上是一种时间和空间高效的数据结构，用于表示字符串集合的所有后缀的 trie。它可以在与 T 中的总字符数成比例的时间内构建(尽管众所周知，这样做的算法很难凭直觉和编写代码)，并且经过精心设计，您可以找到所有与问题文本字符串匹配的根植于时间为 O(k) 的给定节点，其中 k 是匹配数。

总而言之，这里的核心思想是对 T 中字符串的所有后缀创建一个 trie，然后使用模式 P 遍历它。为了时间和空间效率，您可以使用后缀 < em>tree 而不是后缀 trie。