algorithm - 谷歌搜索结果 : How to find the minimum window that contains all the search keywords?

Question

用于查找包含所有搜索关键字的最小片段的算法的复杂性是多少？

Answer 1

如前所述，这个问题是通过一个相当简单的算法解决的:

只需从头开始按顺序查看输入文本并检查每个单词:它是否在搜索关键字中。如果单词在键中，则将其添加到我们将称为当前 block 的结构的末尾。当前 block 只是单词的线性序列，每个单词都伴随着它在文本中的位置。当前 block 必须维护以下属性:当前 block 中的第一个单词必须在当前 block 中出现一次且仅出现一次。如果将新单词添加到当前 block 的末尾，并且违反了上述属性，则必须从 block 中删除第一个单词。此过程称为当前 block 的规范化。规范化是一个潜在的迭代过程，因为一旦您从 block 中删除第一个单词，新的第一个单词也可能违反该属性，因此您也必须将其删除。等等。

因此，当前 block 基本上是一个 FIFO 序列:新词到达右端，并通过规范化过程从左端移除。

解决问题所需要做的就是浏览文本，维护当前 block ，在必要时对其进行规范化，使其满足属性。您构建的包含所有关键字的最短 block 就是问题的答案。

例如，考虑文本

CxxxAxxxBxxAxxCxBAxxxC

使用关键字 A、B 和 C。通过阅读文本，您将构建以下 block 序列

C
CA
CAB - all words, length 9 (CxxxAxxxB...)
CABA - all words, length 12 (CxxxAxxxBxxA...)
CABAC - violates The Property, remove first C
ABAC - violates The Property, remove first A
BAC - all words, length 7 (...BxxAxxC...)
BACB - violates The Property, remove first B
ACB - all words, length 6 (...AxxCxB...)
ACBA - violates The Property, remove first A
CBA - all words, length 4 (...CxBA...)
CBAC - violates The Property, remove first C
BAC - all words, length 6 (...BAxxxC)

我们构建的最佳 block 的长度为 4，这是本例中的答案

CxxxAxxxBxxAxx CxBA xxxC

此算法的确切复杂度取决于输入，因为它决定了规范化过程将进行多少次迭代，但忽略规范化，复杂度将是 O(N * log M)，其中N是文本中的单词数，M是关键词的数量，O(log M)是检查的复杂度当前词是否属于关键字集合。

现在，话虽如此，我不得不承认我怀疑这可能不是您所需要的。由于您在标题中提到了 Google，因此您在帖子中给出的问题陈述可能不完整。也许在您的情况下，文本已编入索引？ (通过索引，上述算法仍然适用，只是变得更有效率)。也许有一些棘手的数据库可以描述文本并允许更有效的解决方案(比如无需查看整个文本)？我只能猜测，你不是说...