When you search in Google or any other search engines, you are provided with a list of links that are relevant to your search query.
In this problem, you are given queries with some candidate results/answers to each query. You have to sort these candidate answers based on their relevance with the respective query.
The relevance is calculated based on counting the number of overlaps of words that occur between each query and the candidate answer.
Here, the overlap is computed based on the following:
If a word x appears in both query A and candidate answer B.
If the similar word of x is y, and if x appears in query A but not in B, and if y appears only in B, then x and y will also be considered as an overlap between A and B.
The overlap between words should be calculated based on the “case insensitive” comparison.If a word x or its similar word y appears more than once in the query or in the candidate answer, it will be counted as only one overlap.
It is to be noted that, one word can have only one similar word. It cannot have multiple different similar words. Uppercase and lowercase versions of a word should be considered as same.
Input
First line of input contains the string “Similar”. Some of the following lines will contain exactly two words (separated by a SPACE) which indicates that these two words are similar to each other i.e the words in each line should be considered as same or as overlap for all queries.
Inputs for similar words list will be ended with the string “Query”. Some of the following lines of input will contain a query and a candidate search result. A query and candidate answer pair is followed by zero or more same queries with different candidate answers in the following lines. In a single line, each query and candidate answer is separated by a TAB character “\t” and each word in the Query and Answer is separated by SPACE.
Input is terminated by the string “QUIT”. You have to sort the search result of each query based on the relevance with the candidate answer.
Constraints
A "word" consists of any ASCII character except any white-space character i.e. SPACE, TAB, NEWLINE etc. List of similar words will not be more than 70 and the total number of query-answer pairs will not be more than 6500. The length of each query can be at most 200 and the length of each answer can be at most 800.
Output
Output the candidate answers of each query based on their relevance with it. The output should be printed by grouping the candidate answers of each distinct query together and sorting them based on their relevance with the query.
Note that, for a single query (which may span through multiple lines), you have to sort its candidate answers together and candidate answer of a different query will not be considered for this query.
In output section, the order of different queries should be strictly maintained based on the order they are given in input. If more than one candidate answers have the same relevance with a given query, then they should appear in the output based on the order they are given in input.
See the sample I/O and Explanation section for better understanding.
Sample
| Input | Output |
|---|---|
Similar win won create created Query Which country won FIFA World Cup 2018 England won ! England have won the Cricket World Cup 2019 Which country won FIFA World Cup 2018 Rafael Nadal won French Open 2019 Which country won FIFA World Cup 2018 France have won the FIFA World Cup 2018 Who created Microsoft Steve Jobs create Apple Who created Microsoft Bill Gates Created Microsoft Who created Microsoft Sergey Brin created Google QUIT | Which country won FIFA World Cup 2018 France have won the FIFA World Cup 2018 Which country won FIFA World Cup 2018 England won ! England have won the Cricket World Cup 2019 Which country won FIFA World Cup 2018 Rafael Nadal won French Open 2019 Who created Microsoft Bill Gates Created Microsoft Who created Microsoft Steve Jobs create Apple Who created Microsoft Sergey Brin created Google |
Explanation
Note that the Query-Answer pairs on lines 5-7 of input are of the same query. Thus the "Answer"s on these lines should be sorted within themselves as they are the only candidates to this particular query.
#1 Which country won FIFA World Cup 2018 -> France have won the FIFA World Cup 2018
#2 Which country won FIFA World Cup 2018 -> England won ! England have won the Cricket World Cup 2019
#3 Which country won FIFA World Cup 2018 -> Rafael Nadal won French Open 2019
#4 Who created Microsoft -> Bill Gates Created Microsoft
#5 Who created Microsoft -> Steve Jobs create Apple
#6 Who created Microsoft -> Sergey Brin created Google
The relevance value for each pair of query-answer is as follows:
#1: Relevance 5
#2: Relevance 3 (The word "won" appears twice in the candidate answer. But it is counted as only one overlap.)
#3: Relevance 1
#4: Relevance 2
#5: Relevance 1
#6: Relevance 1
