ポスティングリストとは、検索語と出現文書 ID の対応関係を持たせたリストである。例えば
などである。
上記のポスティングリストから、and 検索をすると、ID 1, 4 の文書がヒットし、or 検索をすると、ID 1, 2, 3, 4, 7, 9 がヒットする。
ここで and 検索とは「どちらのリストにも含まれる要素を列挙する」ことであり、 or 検索とは「少なくともどちらか一方のリストに含まれる要素を列挙する」ことである。
ポスティングリストが与えられるので、and 検索と or 検索の結果をそれぞれ出力せよ。
n m a_1 a_2 $\ldots$ a_n b_1 b_2 $\ldots$ b_m
入力はすべて整数からなる。
1 行目には検索すべき 2 つのポスティングリストの長さ n と m が空白区切りで与えられる。
2 行目と 3 行目にはそれぞれのポスティングリストに含まれる ID が空白区切りで与えられる。
and 検索のヒット数を A、or 検索のヒット数を B とする。
最初の一行に A B の順に空白区切りで出力せよ。
続く A 行に and 検索でヒットした ID を昇順に出力せよ。
続く B 行に or 検索でヒットした ID を昇順に出力せよ。
4 4 1 2 4 9 1 3 4 7
2 6 1 4 1 2 3 4 7 9
4 4 1 3 5 7 2 4 6 8
0 8 1 2 3 4 5 6 7 8
3 5 1 2 3 1 2 3 4 5
3 5 1 2 3 1 2 3 4 5