查找与查询匹配的所有名称：如何使用后缀树？

Question

问题：你有一部智能手机，你打开了联系人应用程序。你想搜索一个联系人。比方说manmohan。但你不记得他的全名。你只记得mohan，所以你开始打字。当你输入'm'时，联系人应用程序将开始搜索具有字母'm'的联系人。假设您在联系人列表("manmohan", "manoj", "raghav","dinesh", "aman")中存储了姓名，现在联系人将显示manmohan,manoj and aman。现在你输入的下一个字符是'''（直到现在你已经键入“mo”）现在结果应该是“man mo han”。你将如何实现这样的数据结构？

我的方法是应用KMP，因为您在所有可用联系人中查找模式“m”，然后选择“mo”。然后显示匹配的字符串。但采访者说这不是有效的。 （我想不出有什么更好的办法。）在离开之前他说有一个算法可以帮助。如果你知道它，你可以解决它。我做不到。 （在离开之前我问了那个标准算法。访问者说：后缀树）。任何人都可以解释请问，它是如何更好？或者哪个是实现这种数据结构的最佳算法。

Answer 1

你试图解决的问题基本上归结为以下几点：给定一个固定的字符串集合和一个只通过追加更改的字符串，如何有效地找到包含该模式的所有字符串作为子字符串？

在字符串上有一个简洁的结果，对于涉及到子字符串搜索的问题通常很有用：字符串P是字符串T的子字符串当且仅当P是至少一个T后缀的前缀。你是否明白了为什么？）

所以想象一下，你把你的银行中的每个名字，并构造所有银行的所有单词的后缀的字典。现在，给定要搜索的模式字符串P，沿着字符串走，读取P的字符。如果你脱离了字符串，那么字符串P不能是任何名字库的子字符串（否则，它应该是T中一个字符串的至少一个后缀的前缀）。否则，你在某个特洛伊节点。然后，以当前访问的节点为根的子树中的所有后缀对应于T中所有名称中的子字符串的所有匹配项，您可以通过DFS找到该子项并记录所有后缀找。

后缀树本质上是一种时间和空间高效的数据结构，用于表示字符串集合中所有后缀的树状结构。它可以在时间上与T中的总字符数成比例地构建（尽管这样做的算法很难直观和编码），并且被设计为使得您可以找到根植于给定节点时间O（k），其中k是匹配的数量。

回顾一下，这里的核心思想是对T中所有字符串的后缀进行排序，然后使用模式P对其进行排序。对于时间和空间效率，您可以使用后缀树而不是后缀trie。