从搜索文档中查找最小片段的算法？
我一直在浏览Skiena出色的“算法设计手册”，并挂断了其中的一项练习。
问题是：“给出一个包含三个单词的搜索字符串，找到包含所有三个搜索单词的文档的最小片段，即其中包含单词最少的片段。您将获得这些单词的索引位置在出现的搜索字符串中，例如word1：（1、4、5），word2：（4、9、10）和word3：（5、6、15）。每个列表均按上述排序。
”
我想出的一切都是O（n ^
2）…这个问题在“排序和搜索”一章中，因此我认为有一种简单而聪明的方法可以做到。我现在正在尝试使用图形进行某些操作，但这似乎有点过头了。
有想法吗？谢谢
回答：
我已经发布了一个相当简单的算法，可以在此答案中准确解决该问题
但是，在该问题中，我们假设输入由文本流表示，并且单词存储在易于搜索的集合中。
在您的情况下，输入的表示方式略有不同：作为一堆矢量，每个单词的位置都已排序。通过将所有这些向量简单地合并为(position,word)按位置排序的对的单个向量，可以很容易地将该表示转换为上述算法所需的形式。通过将原始向量放入优先级队列（根据其第一个元素排序），可以从字面上完成，也可以“虚拟”完成。在这种情况下，从队列中弹出元素意味着从队列中的第一矢量弹出第一元素，并可能根据其新的第一元素将第一矢量沉入队列。
当然，由于对问题的陈述将单词的数量明确地固定为 3
，因此您可以简单地检查所有三个数组的第一个元素，并在每次迭代时弹出最小的一个。这为您提供了一种O(N)算法，其中N是所有数组的总长度。
同样，您对问题的陈述似乎暗示目标词可以在文本中重叠，这很奇怪（假设您使用术语“词”）。这是故意的吗？无论如何，以上链接的算法都不会出现任何问题。
以上是 从搜索文档中查找最小片段的算法？ 的全部内容， 来源链接： utcz.com/qa/402183.html
