绿了，儿子的卡卡没收到呢…… - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>EB23 - 劳工卡

绿了，儿子的卡卡没收到呢……

绿了，儿子的卡卡没收到呢……# EB23 - 劳工卡

b*72011-10-24 07:10

1 楼

以前听论坛上有人提过，但是没给过解，不知道哪位大侠能偶赐教啊！
Given a document and a query of K words, how do u 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). This one is really hard. Could someone propose an
algorithm in O(n)?

m*o2011-10-24 07:10

2 楼

5月，NSC，终于绿了……郁闷的是，儿子的绿卡没收到……大家的卡都是一起寄来的吗
？还是分着收到的~~~发10个包子吧，实力有限~~~

p*92011-10-24 07:10

3 楼

The question looks not quite clear. If we already know the positions for all
keys, we can find the min cover in O(n). Without the assumption, the
complexity of finding words from document is larger than O(n).

an

【在 b******7 的大作中提到】

: 以前听论坛上有人提过，但是没给过解，不知道哪位大侠能偶赐教啊！
: Given a document and a query of K words, how do u 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). This one is really hard. Could someone propose an
: algorithm in O(n)?

I*12011-10-24 07:10

4 楼

gxgx

【在 m*****o 的大作中提到】

: 5月，NSC，终于绿了……郁闷的是，儿子的绿卡没收到……大家的卡都是一起寄来的吗
: ？还是分着收到的~~~发10个包子吧，实力有限~~~

r*u2011-10-24 07:10

5 楼

my 2 cents:
given: a p o p g o a, find the window that covers all the chars. You can
think it this way:
a p o p g o a
a 1-----------7
p 2---4
o 3-----6
g 5
Here, we have 4 different chars. You can consider the appear of each one
as a segment, as shown above. You need to find a segment which overlaps the
segment of every char. In this example, it should be 1->6. Some
computational geometry problem.

all

【在 p*********9 的大作中提到】

: The question looks not quite clear. If we already know the positions for all
: keys, we can find the min cover in O(n). Without the assumption, the
: complexity of finding words from document is larger than O(n).
:
: an

IC2011-10-24 07:10

6 楼

恭喜，分开寄的

【在 m*****o 的大作中提到】

: 5月，NSC，终于绿了……郁闷的是，儿子的绿卡没收到……大家的卡都是一起寄来的吗
: ？还是分着收到的~~~发10个包子吧，实力有限~~~

p*92011-10-24 07:10

7 楼

no. In your example, the min cover should 4->7.

the

【在 r**u 的大作中提到】

: my 2 cents:
: given: a p o p g o a, find the window that covers all the chars. You can
: think it this way:
: a p o p g o a
: a 1-----------7
: p 2---4
: o 3-----6
: g 5
: Here, we have 4 different chars. You can consider the appear of each one
: as a segment, as shown above. You need to find a segment which overlaps the

j*k2011-10-24 07:10

8 楼

gxgx

【在 m*****o 的大作中提到】

: 5月，NSC，终于绿了……郁闷的是，儿子的绿卡没收到……大家的卡都是一起寄来的吗
: ？还是分着收到的~~~发10个包子吧，实力有限~~~

r*u2011-10-24 07:10

9 楼

You are right. But, the idea should be correct.

【在 p*********9 的大作中提到】

: no. In your example, the min cover should 4->7.
:
: the

n*a2011-10-24 07:10

10 楼

Gx

5月，NSC，终于绿了……郁闷的是，儿子的绿卡没收到……大家的卡都是一起寄来的吗
？还是分着收到的~~~发10个包子吧，实力有限~~~
★ Sent from iPhone App: iReader Mitbbs Lite 7.28

【在 m*****o 的大作中提到】

: 5月，NSC，终于绿了……郁闷的是，儿子的绿卡没收到……大家的卡都是一起寄来的吗
: ？还是分着收到的~~~发10个包子吧，实力有限~~~

c*a2011-10-24 07:10

11 楼

agree

【在 p*********9 的大作中提到】

: no. In your example, the min cover should 4->7.
:
: the

a*o2011-10-24 07:10

12 楼

gx

【在 m*****o 的大作中提到】

: 5月，NSC，终于绿了……郁闷的是，儿子的绿卡没收到……大家的卡都是一起寄来的吗
: ？还是分着收到的~~~发10个包子吧，实力有限~~~

g*y2011-10-24 07:10

13 楼

seems like:
you have K arrays of integers:
example: K=3
arr1: 1, 3, 4, 7, 14
arr2: 2, 5, 8, 15...
arr3: 3, 12, 13, 19 ...
arrK[i] is the position of ith ocurrence of the k-th word in the doc.
question: find min{distance(i,j,k)}
where:
distance(i,j,k) = max{|arr1[i]-arr2[j]|,|arr1[i]-arr3[k]|,|arr2[j]-arr3[k]|}
This is very easy and can be done in one scan of K arrays. Complexity is O(K*N)
Hint: just try plot some dots on the two/three number axis to represent two/three arrays, and keep in mind t

a*x2011-10-24 07:10

14 楼

chi

【在 m*****o 的大作中提到】

: 5月，NSC，终于绿了……郁闷的是，儿子的绿卡没收到……大家的卡都是一起寄来的吗
: ？还是分着收到的~~~发10个包子吧，实力有限~~~

g*y2011-10-24 07:10

15 楼

"Some computational geometry problem."
you are bluffing!

the

【在 r**u 的大作中提到】

l*e2011-10-24 07:10

16 楼

Cong~~~~~~~~
Chi baozi
Thanks

【在 m*****o 的大作中提到】

: 5月，NSC，终于绿了……郁闷的是，儿子的绿卡没收到……大家的卡都是一起寄来的吗
: ？还是分着收到的~~~发10个包子吧，实力有限~~~

s*82011-10-24 07:10

17 楼

a p o p g o a
a0p0o0g0 count=0
[a] p o p g o a
a1p0o0g0 count=1
[a p] o p g o a
a1p1o0g0 count=2
[a p o] p g o a
a1p1o1g0 count = 3
[a p o p] g o a
a1p2o1g0 count = 3
[a p o p g] o a
a1p2o1g1 count = 4 (mark, pos 0-4, length 5)
a [p o p g] o a
a0p2o1g1 count = 3
a [p o p g o] a
a0p2o2g1 count = 3
a [p o p g o a]
a1p2o2g1 count = 4 (pos 1-6, length 6, worse than previous, ignore)
a p [o p g o a]
a1p1o2g1 count = 4 (pos 2-6, length 5, equal to previous mark, ignore)
a p o [p g o a]
a1p1o