COMPANY XXX is particularly interested in improving the volume and quality of traffic to our public facing web sites from search engines. Many of these search engines are quite sophisticated, using advanced algorithms and parallel searching techniques to provide fast, accurate responses.This problem is however, somewhat simpler.
A group of web pages has been classified by associating a list of keywords, given in decreasing order of relevance, with each page (i.e., the order of keywords is from the most specific keyword to the least specific). For example, on the TopGear website a page on reviews of Ford cars may have the keywords: Ford, Car, Review in that order; the most relevant keyword is Ford.
Queries also include a list of keywords, again from most to least relevant. For example, in a query consisting of the keyword Ford followed by the keyword Car, Ford is more important than Car.
In this problem you are to determine the top five (or fewer) pages that match each of an arbitrary number of queries
To determine the strength of the relationship between a query and a web page, assume the keywords for each page and each query are assigned integer weights, in descending order, starting with N, where N is the maximum number of keywords allowed for a web page and query.
The strength of the relationship is the sum of the products of the weights associated with each keyword that appears both in the webpage list and the query list.
For example, assume the following web pages and keyword lists: Page 1: Ford, Car, Review Page 2: Toyota, Car, Page Page 3: Car, Ford
For N equal 8, a query with keywords Ford and Car in that order yields the following strength ratings.
Page 1: (8x8 + 7x7) = 113 Page 2: (7x7) = 49 Page 3: (7x8 + 8x7) = 112
Similarly, a query with keywords Ford and Review yields the following strength ratings.
Page 1: (8x8 + 7x6) = 106 Page 2: = 0 Page 3: (8x7) = 56
Input Input data consist of one line for each web page and query. A line consists of a code letter followed by a list of keywords. Code letters P and Q denote a page and a query. Code letters and keywords are separated by at least one space. Ps and Qs may occur in any order. Pages are added sequentially starting with page one. The case of characters in the keywords is not significant. Each query also has a list of between one and 8 keywords. Again, case being insignificant for keywords. Number the queries sequentially starting with one.
Output For each query, identify the 5 (or fewer) pages stored that are the most relevant to the query. Print a single line containing the query identifier, a colon, and the page identifiers of the five most relevant pages in the decreasing order of relevance. Page identifiers consist of the letter “P” followed by the page number. Query identifiers consist of the letter “Q” followed by the query number. If several pages have the same relevance, list them by increasing page number. Do not list pages that have no relationship (zero strength), even if fewer than five pages are identified.
Additional Considerations Although the search strength algorithm described here is quite simple, developers should make provision for substituting a more complex method in the future and consider the impact of nested pages.
Sample Input P1 Ford Car Review P2 Review Car P3 Review Ford P4 Toyota Car P5 Honda Car P6 Car
Q1 Ford Q2 Car Q3 Review Q4 Ford Review Q5 Ford Car Q6 cooking French Output for the Sample Input Q1: P1 P3 Q2: P6 P1 P2 P4 P5 Q3: P2 P3 P1 Q4: P3 P1 P2 Q5: P1 P3 P6 P2 P4 Q6: