data-structures - 词汇表中模式匹配的最佳数据结构是什么？

Question

给定一组词汇表，什么是最好的数据结构，可以用来查找词汇表中与给定子字符串匹配的所有单词？

假设“Ap”是子字符串，
应该返回“Apple”和“Application”。
由于在这种情况下，“Ap”在两个字符串的开头，我可以想到使用Tries。

但是如果要匹配的子串可以在词汇表中的任何地方找到呢？
例如：如果给出“ap”，则还应返回“shape”，因为“ap”出现在“shape”中。

词汇集非常大。

Answer 1

你想要的是一个后缀树。这会将（一组）字符串的所有后缀存储在一个特里（在您的情况下，是一组单词）。trie 的每个叶子都与具有该后缀的字符串集相关联。

搜索子串时，只需匹配 trie 根的子串即可；您的子字符串必须是某个后缀的前缀，否则不匹配。发现匹配的存在是子字符串长度的线性时间。要确定所有匹配的单词，您必须枚举从匹配完成点可访问的树的所有叶子。那是一个树行走问题；如果树有明显的分支，它可能会有点贵。

您可以为每个 trie 节点预先计算相关联的单词集；这可能非常大，但是现在您可以非常快速地确定匹配的单词。

如果您只需要检查集合的成员，直到找到具有一些不错属性的成员，我会坚持使用枚举。