Consultas sobre el Sufijo Común Más Largo (Longest Common Suffix Queries)
(Rap battle)
Se te proporciona una lista de
n palabras distintas: , y una lista de q palabras de consulta: . Tu objetivo es encontrar, para cada palabra de consulta w, la palabra de la lista a que sea distinta de w y que comparta el sufijo común más largo con w. En caso de que varias palabras tengan el mismo sufijo común, deberás devolver la que sea lexicográficamente más pequeña.Entrada
La primera línea de la entrada contiene un único entero,
n (2 ≤ n ≤ 25 000), que indica la cantidad de cadenas en la lista.Las siguientes
n líneas contienen las cadenas. Cada cadena está compuesta de letras minúsculas del inglés y su longitud no excede los 30 caracteres.La línea siguiente contiene un único entero,
q (1 ≤ q ≤ 25 000), que indica la cantidad de cadenas de consulta.Las
q líneas siguientes contienen las palabras de consulta.Cada cadena está compuesta de letras minúsculas del inglés y su longitud no excede los 30 caracteres.
Salida
Para cada palabra de consulta, imprime en una línea la palabra de la lista que sea diferente de la de consulta y que comparta el sufijo común más largo con ella. En caso de empate en la longitud del sufijo, se imprime la palabra que sea lexicográficamente más pequeña.
Ejemplos
Entrada | Salida |
4
perfect
rhyme
crime
time
2
crime
rhyme | time
crime |
Constraints
Time limit: 5 seconds
Memory limit: 512 MB
Output limit: 1 MB