※ 引述《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] ?