Consultas do Maior Sufixo Comum
(Batalha de rap)
Recebe-se uma lista de
n palavras distintas: , bem como uma lista de q palavras de consulta . O objetivo é encontrar, entre a lista a, a palavra lexicograficamente menor que seja diferente de w e que partilhe com w o maior sufixo comum.Entrada
A primeira linha da entrada contém um único número inteiro,
n (2 ≤ n ≤ 25 000), que representa a quantidade de strings na lista.As
n linhas seguintes contêm essas strings. Cada string é formada por letras minúsculas do alfabeto inglês e o comprimento de cada string não excede 30 caracteres.A linha seguinte contém um único número inteiro,
q (1 ≤ q ≤ 25 000), representando o número de strings para consulta.As
q linhas seguintes contêm as palavras de consulta.Cada uma dessas palavras é formada por letras minúsculas do alfabeto inglês e o seu comprimento não excede 30 caracteres.
Saída
Para cada palavra de consulta, deve-se apresentar uma única linha com a palavra lexicograficamente menor, presente na lista, que seja diferente da palavra consultada e que partilhe com ela o sufixo mais longo possível.
Exemplos
Entrada | Saída |
4
perfect
rhyme
crime
time
2
crime
rhyme | time
crime |
Constraints
Time limit: 5 seconds
Memory limit: 512 MB
Output limit: 1 MB