algorithm - 大文本中给定关键字的最短短语的长度

Question

这个问题是在采访中问我的一个 friend 的。

给定两个关键字，我们必须在大文本中找到具有给定关键字的最短短语的长度。 关键字可以在该文本中以任何顺序出现。 约束:保持高效的数据结构，这样每次使用不同关键字的查询都不需要解析文本

eg. keywords: "one", "four" text: "one two three four five four six one"

here the shortest such phrase is "four six one" rather than "one two three four"

我们想到的解决方案是: 用文本中的所有单词构建一个 BST。每个节点维护单词的位置。 (这将是一个排序列表)当一个查询来搜索 [O(logn)] 两个词时，找到它们在 [O(n)] 中位置之间的最小差异从而使其有效地 [O(nlogn)]。

我们可以做得更好吗？

Answer 1

您可以使用哈希表作为反向索引，即从单词(关键字)到它们在文本中位置的排序列表的哈希表。得到query的两个关键词后，再去查找他们的出现记录就是O(1)的操作。

找到关联位置之间的最小差异是 O(k) 操作，其中 k 是较长关联列表的长度。在异常情况下，k 可能接近 n，但在实际使用中并非如此(除非您使用“the”和“a”作为两个关键字，但这些类型的词，称为停用词，通常被排除在完整仍然是文本搜索)。

在通常情况下，k 与 n 相比非常小，因此这应该非常快，即 O(1) + O(更常见关键字的出现次数)。