hw搜索索引字符串列表中的子字符串？

Question

我正在实现字典，其中键是一个字符串keyword.suppose我有以下键字典。

垫黉 坐在黉 LAT 黉

现在如果我检索算法单个关键字假设mathon它会搜索它在不断的时间。但如果我要搜索黉我希望所有三个单词的时间要么在最短的时间内被恢复，就像在谷歌搜索的情况下一样。我应该怎么做？ 并且是目的字典正确的数据结构？

字典的价值是我需要显示给用户和搜索可以是多个关键字的项目列表。

Answer 1

gaddag，如this paper中所述，可能是您最好的选择。它是一种变体，可以让你在单词的任何地方开始搜索，并且可以向前和向后走。它不是O（1）查找，但速度非常快，并具有合理的空间使用情况。

编辑：并且对于多个关键字，您可以简单地在每个关键字上单独搜索，然后根据设置确定相交或联合。它可能比你想象的要快;至少值得作为最简单可能的算法来实现，并且只有在分析时证明它是实际的瓶颈时才会丢弃。