Google搜索结果:如何查找包含所有搜索关键字的最小窗口？

Question

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

Answer 1

如上所述,问题通过一个相当简单的算法解决:

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

因此,基本上当前块是一个FIFO序列:新词到达右端,并从左端通过归一化过程删除.

解决问题所需要做的就是查看文本,维护当前块,在必要时对其进行标准化,使其满足"属性".您构建的所有关键字中最短的块是问题的答案.

例如,考虑文本

CxxxAxxxBxxAxxCxBAxxxC

使用关键字A,B和C.查看文本,您将构建以下序列块

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)

我们建造的最佳街区长度为4,这是本案的答案

CxxxAxxxBxxAxx CxBA xxxC

这种算法的确切复杂性取决于输入,因为它决定了规范化过程将进行多少次迭代,但是忽略了复杂性的标准化O(N * log M),N文本中的单词M数量和关键字的数量,以及O(log M)检查当前单词是否属于关键字集的复杂性.

现在,说了这些,我不得不承认我怀疑这可能不是你需要的.由于您在标题中提到了Google,因此您在帖子中提供的问题声明可能不完整.也许在你的情况下文本被索引？(使用索引上述算法仍然适用,只是变得更有效率).也许有一些棘手的数据库描述文本并允许更有效的解决方案(如不查看整个文本)？我只能猜测,你不是说......