Retos - 015: Colección de música

Nivel de dificultad aproximado (1 a 5): 4  

Phil Audio tiene una gran colección de música, y es muy particular con las canciones que escucha. Cada canción tiene un nombre, que es una cadena de caracteres. Su reproductor de música tiene una función de búsqueda que permite a Phil escribir una subcadena en el cuadro de búsqueda, y el reproductor, a continuación, enumera todas las canciones cuyos nombres contengan la subcadena. Si no es exactamente una canción que coincide con la búsqueda, entonces Phil lo puede pulsar la tecla Intro para escuchar esa canción.

Phil odia usar el ratón, y que no le gusta escribir mucho, así que insiste en escribir siempre la subcadena más breve posible que coincide exactamente con la canción que quiere escuchar en este momento. ¿Podrías ayudarle a encontrar a su consulta de búsqueda óptima?

 

Entrada

La primera línea de la entrada da el número de casos de prueba (T), y a continuación los T casos de prueba. Cada uno comienza con una línea que contiene un único número de N. Las siguientes N líneas contienen un nombre de la canción cada una (que son todas las canciones de la colección de Phil).

Cada nombre de canción estará formado por letras, espacios y el carácter guión (-). Todas las canciones de la colección de Phil son únicas (no hay duplicadaos) y de no más de 100 caracteres de longitud. Los nombres de las canciones pueden estar en mayúsculas y minúsculas, por lo que "dZihan" es la misma es "Dzihan". El algoritmo de búsqueda es también insensible a mayúsculas y minúsculas.

Salida

Para cada caso de prueba, la salida comenzará con una línea que contiene "Caso #x:", donde x es el número de caso (a partir de 1). Después de eso, se mostrarán las N líneas, una para cada canción en la recopilación de Phil, en el orden que las canciones se dieron en la entrada. Para cada canción, se debe imprimir la cadena de caracteres más corta que se encuentra únicamente en esa canción. Si hay varias respuestas correctas, se tomará la primera en orden lexicográfico. Se debe mostrar comillas alrededor de cada cadena. Si no hay una respuesta correcta, se escribirá ":(" sin las comillas dobles.

Tenga en cuenta que las letras mayúsculas aparecen lexicográficamente antes de letras minúsculas, el guión está antes que todas las letras, y en el espacio está antes de guión.

(Asegúrate de que has leído las preguntas frecuentes antes de plantear tu solución)

Ejemplo

Entrada
5
6
A Perfect Circle - Gravity
Aimee Mann - You Do
Aqualung - Cinderella
Arcade Fire - Haiti
Art of Noise - Pleure
ATB - Marrakech
2
Hybrid - Altitude
Kings of Convenience - The Build-up
3
aaaaaaaabb
aaaaaaabbb
ababababab
3
butter
fly
butterfly
1
Unknown Artist - Track One

Salida
Caso #1:
"V"
" D"
"Q"
" F"
"S"
"B"
Caso #2:
"A"
"C"
Caso #3:
"AAAAAAAA"
"BBB"
"BA"
Caso #4:
:(
:(
"RF"
Caso #5:
""

Aportar una solución

Tu nombre (si quieres que aparezca):
Tu web/blog (si quieres que incluyamos un enlace a ella):
Tu e-mail (no se mostrará; si quieres que te avisemos cuando esté publicado):
¿Eres humano? ¿Cuánto es 2 más 3?
Lenguaje
Fuente: