JDCC '15 Contest 2 P3 - eLettery

View as PDF

Submit solution

Points: 5
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type

You have been hired by a dating site to code their incredibly advanced matching algorithm. The site has found that the best indicator of a good couple is how many letters their names share: the more the better!

For example, Charles and Kate share two letters: they are an okay match. John and Johnina, on the other hand, share four letters: they are a great match! Given a person and a list of potential partners, find the best match.

Input Specification

The first line of the input provides the number of test cases, T (1 \le T \le 100). T test cases follow. Each test case begins with a string S, a person's name, and N (1 \le N \le 1 000), the number of potential partners. N lines follow, each containing one name. The names will appear in alphabetical order and will be entirely capitalized.

Output Specification

For each test case, output the name of the best partner. If multiple partners share the same number of letters with the person, output the name which comes first alphabetically.

Sample Input

2
SARAH 3
AARON
ASHLEY
SAHAR
MEAGAN 3
ANDREW
ANN
JANE

Sample Output

SAHAR
ANDREW

Explanation for Sample

In the first test case, Sarah shares three letters (a, r, a) with Aaron, three (s, a, h) with Ashley, and five letters with Sahar, so Sahar is the best match.

In the second test case, Meagan shares three letters (e, a, n) with Andrew, two (a, n) with Ann, and three (e, a, n) with Jane. Since Andrew's name comes first alphabetically, he's chosen as the best match.


Comments

There are no comments at the moment.