algorithm - 在 O(n) 时间内从包含属于给定查询的所有单词的段落中找到最小长度的片段

Question

给定一个评论段落和关键字，从包含所有关键字的段落中找到最小长度的片段，该片段以任意顺序包含。如果有数百万条评论，您将执行什么预处理步骤。第一部分很简单，就是最小窗口问题。现在，对于预处理，我使用倒排索引。因此，对于每次评论，我都会建立一个表来存储每个单词的出现列表。现在，当查询到来时，我检索每个单词的索引列表。现在，有没有办法在 O(n) 时间内从这组列表中找出最小窗口长度？我尝试构建最小和最大堆来存储每个列表的当前索引，然后跟踪最小窗口长度(使用两个堆的根)。然后我执行 extractMin 操作并从最大堆中删除相同的元素。为了保留最大堆中每个元素的位置地址(用于删除)，我维护了一个哈希表。现在，从提取的元素所属的列表中，我将下一个元素插入到两个堆中，并根据需要更改窗口长度。这需要 O(nlog n) 时间。是否可以在 O(n) 时间内完成？

Answer 1

假设这个组合在这里排序是我会怎么做:

• 创建描述单词及其索引的对象列表，类似于 Obj(String name,Int index)。
• 初始化一个包含查询的所有关键字的集合。
• 将窗口的下界初始化为列表中第一个元素的索引。
• 遍历列表，将窗口的上限更新为当前对象的索引，将窗口的下限更新为查询中任何单词首次出现的索引(即一旦 min_window 设置为实际单词出现的索引(不再更新)并从关键字集中删除相应的单词。
• 当集合为空时，保存生成的下限和上限以及片段的长度。
• 重复步骤 2 到 5，但这次您要使用的列表是从紧接在前一个 min_window 定义的元素之后的元素开始的列表，如果长度为 min_window 和 max_window片段的一部分比前一个短(应重复此片段，直到您无法再在给定的子列表中找到所有出现的片段)。