키워드 일치도 계산

검색 엔진은 사용자가 입력한 조건에 맞는 페이지를 찾아준다. 실제 검색 엔진은 빠르고 정확한 응답을 위해 복잡한 알고리즘을 사용하지만, 이 문제에서는 단순한 방식으로 페이지와 질의의 관련도를 계산한다.

여러 웹 페이지가 주어진다. 각 페이지는 1개 이상 8개 이하의 키워드로 분류되어 있으며, 한 페이지 안의 키워드는 관련성이 높은 순서부터 낮은 순서로 주어진다. 예를 들어 Smalltalk의 programming을 다루는 페이지가 Smalltalk, programming, computers 세 키워드를 이 순서로 가진다면, 가장 관련성이 높은 키워드는 Smalltalk이다.

질의도 1개 이상 8개 이하의 키워드로 이루어지며, 역시 중요한 키워드부터 순서대로 주어진다. 질의에서 Smalltalk가 computers보다 앞에 있다면 Smalltalk가 더 중요한 키워드이다.

각 질의에 대해 관련도가 가장 높은 페이지를 최대 5개까지 찾아야 한다. 관련도를 계산할 때, 페이지와 질의에 있는 각 키워드에는 위치에 따라 가중치가 붙는다. 첫 번째 키워드의 가중치는 8이고, 이후 키워드의 가중치는 한 자리씩 뒤로 갈 때마다 1씩 줄어든다.

한 키워드가 페이지와 질의에 모두 등장하면, 그 키워드가 페이지에서 가진 가중치와 질의에서 가진 가중치를 곱한다. 한 페이지와 한 질의의 관련도는 이렇게 얻은 곱을 모든 공통 키워드에 대해 더한 값이다.

예를 들어 다음 세 페이지가 있다고 하자.

• Page 1: Smalltalk, programming, computers
• Page 2: computers, programming
• Page 3: computers, Smalltalk

질의가 Smalltalk programming이면 각 페이지의 관련도는 Page 1이 113(= 8 x 8 + 7 x 7), Page 2가 49(= 7 x 7), Page 3이 56(= 8 x 7)이다. 질의가 Smalltalk computers이면 각 페이지의 관련도는 Page 1이 106(= 8 x 8 + 7 x 6), Page 2가 56(= 7 x 8), Page 3이 112(= 8 x 7 + 7 x 8)이다.

입력은 웹 페이지 또는 질의를 나타내는 여러 줄로 이루어진다. 각 줄은 식별 문자와 키워드 목록으로 구성된다.

식별 문자는 P, Q, E 중 하나이다.

• P: 웹 페이지
• Q: 질의
• E: 입력의 끝

식별 문자와 첫 번째 키워드 사이에는 하나 이상의 공백 문자가 있다. P와 Q 줄은 어떤 순서로도 나타날 수 있다. 페이지는 입력에 등장한 순서대로 1번부터 번호가 붙고, 질의도 입력에 등장한 순서대로 1번부터 번호가 붙는다.

각 페이지는 1개 이상 8개 이하의 키워드를 가진다. 각 키워드의 길이는 20자를 넘지 않는다. 입력에는 최대 25개의 페이지가 등장한다.

각 질의도 1개 이상 8개 이하의 키워드를 가진다. 각 키워드의 길이는 20자를 넘지 않는다.

키워드는 대소문자를 구분하지 않는다.

각 질의마다 한 줄을 출력한다. 출력 형식은 질의 식별자, 콜론(:), 그리고 관련도가 높은 페이지 식별자를 순서대로 나열한 형태이다.

페이지 식별자는 P# 형식이며, #은 페이지 번호이다. 질의 식별자는 Q# 형식이며, #은 질의 번호이다.

각 질의에 대해 관련도가 양수인 페이지 중 관련도가 높은 순서대로 최대 5개를 출력한다. 관련도가 같은 페이지가 여러 개라면 페이지 번호가 작은 순서대로 출력한다. 관련도가 0인 페이지는 출력하지 않는다.