Query sul Sufisso Comune Più Lungo
(Battaglia rap)
Vi viene fornito un elenco di
n parole distinte: , insieme a un elenco di q parole di query . Il vostro compito è trovare, all’interno della lista a, la parola che sia diversa da w e che abbia con w il suffisso comune più lungo, scegliendo poi quella lessicograficamente più piccola.Input
La prima riga dell’input contiene un singolo intero,
n (2 ≤ n ≤ 25 000), che indica il numero di stringhe presenti nella lista.Le successive
n righe contengono le stringhe. Ogni stringa è composta esclusivamente da lettere minuscole inglesi e la lunghezza di ciascuna non supera i 30 caratteri.La riga successiva contiene un singolo intero,
q (1 ≤ q ≤ 25 000), che rappresenta il numero di query.Le seguenti
q righe contengono le parole di query.Ciascuna parola è composta da lettere minuscole inglesi e la lunghezza non supera i 30 caratteri.
Output
Per ogni query, occorre stampare su una singola riga la parola, in
a, che sia diversa da quella di query e che abbia il suffisso comune più lungo con la parola di query, selezionando quella lessicograficamente più piccola.Esempi
Ingresso | Uscita |
4
perfect
rhyme
crime
time
2
crime
rhyme | time
crime |
Constraints
Time limit: 5 seconds
Memory limit: 512 MB
Output limit: 1 MB