컴퓨터 과학

컴퓨터 과학은 컴퓨터와 관련 기술을 이용해 현실의 문제를 푸는 방법을 연구하며, 매우 많은 주제를 아우른다. 최근의 대표적인 성공 사례 중 하나는 정보를 정리하고 검색하는 일이다. 웹 검색이 우리 삶을 얼마나 바꾸어 놓았는지 떠올려 보라. 여기서는 아주 단순한 형태의 웹 검색 엔진을 다룬다.

여러 개의 문서가 주어진다. 각 문서는 단어와 하이퍼링크로 이루어지며(HTML보다 단순한 형식이다), 한 단어짜리 질의도 함께 주어진다. 우리는 각 질의에 대해 가장 관련성이 높은 페이지를 찾아야 한다. 페이지 $P$가 관련 있다고 보는 이유는 두 가지다. (1) 질의어가 $P$ 안에 등장하거나, (2) 질의어가 $P$로 연결되는 다른 페이지에서 그 하이퍼링크와 가까운 위치에 등장하는 경우다.

점수 계산. 질의어를 $q$라 하자.

• $P$ 안에 $q$가 등장할 때마다 $P$는 $1$점을 얻는다.
• 어떤 페이지 $P'$에서 $P$로 향하는 하이퍼링크 $L$이 있을 때, $P'$ 안에서 $L$과의 단어 거리가 $d$인 $q$의 등장마다 $P$는 $\max(4 - d, 0)$점을 얻는다. 즉 $d < 4$이면 $4 - d$점을, 그렇지 않으면 $0$점을 얻는다.

하이퍼링크에 표시되는 단어 자체도 문서의 한 단어다. 그 단어가 $q$와 같으면 등장으로 세며, 거리를 잴 때도 자신의 위치를 차지한다. 특히 하이퍼링크 $L$의 표시 단어가 곧 $q$라면 그 등장은 거리 $d = 0$이므로 $4$점의 가치를 지닌다. 거리는 줄바꿈을 무시하고 문서 전체를 하나의 단어열로 보아 단어 단위로 센다. $P'$ 안의 같은 등장이 $P$를 가리키는 여러 하이퍼링크와 가깝다면, 그만큼 여러 번 중복해서 셀 수 있다.

참고: 사실 (2)번 이유가 더 중요할 때가 많다. 다른 페이지가 당신을 링크하며 당신에 대해 하는 말이, 당신 스스로 하는 말보다 더 나은 설명인 경우가 흔하기 때문이다. 그 이유는 페이지가 스스로에 대한 설명을 스팸처럼 부풀릴 수 있다는 점, 그리고 페이지가 관련된 모든 용어를 담고 있지는 않다는 점이다.

첫 줄에는 데이터 집합의 개수를 뜻하는 정수 $K \ge 1$이 주어진다. 이어서 $K$개의 데이터 집합이 다음 형식으로 주어진다.

각 데이터 집합의 첫 줄에는 두 정수 $m$과 $n$이 주어진다. 각각 질의의 개수와 웹 페이지의 개수이며, 둘 다 $1$ 이상 $100$ 이하다.

다음 $m$개의 줄에는 질의가 한 줄에 하나씩 주어진다. 각 질의는 소문자 알파벳으로만 이루어진 최대 $20$글자의 한 단어다.

그다음에는 $n$개의 웹 페이지에 대한 설명이 주어진다. $i$번째 페이지의 설명은 그 페이지를 이루는 줄 수 $\ell_i$($1$ 이상 $100$ 이하)가 적힌 줄로 시작하고, 이어서 각각 최대 $255$글자인 $\ell_i$개의 텍스트 줄이 온다. 각 텍스트 줄은 공백으로 구분된 단어들의 나열이다. 모든 단어는 소문자 알파벳으로만 이루어지며 길이는 최대 $20$글자다.

일부 단어는 하이퍼링크다. 하이퍼링크는 표시할 단어와 연결 대상 페이지 번호를 대괄호로 묶어 나타낸다. 예를 들어 [usc,3]은 표시 단어가 usc이고 대상이 $3$번 페이지인 하이퍼링크다. 대상 번호는 항상 $1$ 이상 $n$ 이하의 올바른 페이지를 가리키며, 자기 자신으로의 링크는 절대 없다.

각 데이터 집합에 대해, 먼저 Data Set x: 한 줄을 출력한다. 여기서 $x$는 데이터 집합의 번호로 $1$부터 시작한다. 그다음 각 질의에 대해 순서대로, 점수가 가장 높은 페이지를 한 줄에 하나씩 출력한다. 최고 점수를 가진 페이지가 여러 개라면, 페이지 번호가 커지는 순서로 한 줄에 공백으로 구분하여 모두 출력한다.