给定一组词汇表，可用于查找词汇表中与给定子字符串匹配的所有单词的最佳数据结构是什么？
假设“Ap”是子字符串，
应返回“Apple”和“Application”。
由于在本例中，“Ap”位于两个字符串的开头，因此我可以想到使用 Tries。
但是如果要匹配的子串可以在词汇表的单词中的任何位置找到怎么办？
例如:如果给出“ap”，则还应返回“shape”，因为“ap”出现在“shape”中。
词汇量非常大。
最佳答案
你想要的是 suffix tree 。这将一个(一组)字符串的所有后缀存储在一个字典树(在您的例子中，是一组单词)中。特里树的每个叶子都与具有该后缀的字符串集相关联。
搜索子字符串时，只需匹配 trie 根部的子字符串即可；您的子字符串必须是某个后缀的前缀，否则不匹配。发现匹配的存在是子字符串长度的线性时间。要确定所有匹配单词，您必须枚举从匹配完成点可访问的所有叶子节点。这是一个树行走问题；如果树有明显的分支，它可能会有点贵。
您可以为每个 trie 节点预先计算关联词的集合；这可能相当大，但现在您可以非常快速地确定匹配的单词。
如果您只需要检查集合中的成员，直到找到具有一些良好属性的成员，那么我会坚持使用枚举。
关于data-structures - 词汇表中模式匹配的最佳数据结构是什么？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/17761469/