※ 引述《Leon (Achilles)》之铭言： : ※ 引述《RockLee (Now of all times)》之铭言： : : 原始网址: : : http://www.careercup.com/question?id=15381730 : : 题目: : : Given a document and a query of K words, : : how do you find the smallest window that covers all the words at least once : : in that document? : : (given you know the inverted lists of all K words, that is, for each word, : : you have a list of all its occurrrences). : : Could someone propose an algorithm in O(n)? : : 假设 occurrrences lists 是 sorted, 用 TreeMap 应可在 O(N*logK) 解决, : : 一开始将每个 occurrrences list 最小的丢入 TreeMap 就可得到第一个 window, : : (key = index in the document, value = the occurrrences list it belonged & its : : index in that occurrrences list), : : 之後将 TreeMap 最小的移除并加入同一个 occurrrences list 的下一个即可移动 : : window, : : 直到任一个 occurrrences list 耗完. : : 但要在 O(N) 的时间内解决就想不出来了... : : 不知道板上有没有人有什麽 idea? : Sorry, I can't understand your writing. : Also, the link seems to be wrong... : Can you describe it, step by step. : For example, there are only 3 words, (a,b,c) : how are you going to find the window, for the document : [b b a c b b b b c b b a] ? 嗯, 刚刚想了一下. 这个题目, 是 KMP 的变形. 难的地方在於, 你怎麽想到正确的方向 (听起来有点废话, 哈哈..) 这里我采用之前的定义. For a sentance, we are given the occurance index. Take above example, say, only 3 words {a, b, c}. The sentance is [b b a c b a]. The the occurance index will be a = {3, 6}. b = {1, 2, 5}. c = {4 }. 在开始之前, 我们先看几个非常简单的作法. 1. Naive: Arbitary choose 2 position from [1, N], then check the condition. 2. Choose one position as the left boundary, then, use the max-min of the rest set the decide the right boundary. For example, if I choose 2 as my left boundary, then I need to choose the right boundary by the max of d(2,3) and d(2,4) which cover set {a} and set {c} The result window is [2, 4]. And the complexity should be O(N* K). 接下来, 就是有趣的地方了. 3. Follow the previous algorithm, inspired by KMP. When we start from 3, actually we don't need to compare all K groups. Because from previous step, we know [2] covers {b} for sure. And [3,4] covers {a,c} for sure. In this case, we only need to check the condition for set {b} ! which is d(3,5). Then the computational complexity is O(N). I'll leave the detail for you. --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 204.140.133.209