Fuzzy Matching (corrispondenza approssimativa)
Immagina di essere uno dei primi ingegneri di Google, con l’incarico di creare una funzionalità in Google Search che verifichi se l’input dell’utente esiste nel database oppure no.
Dal momento che stai appena iniziando a lavorare sull’algoritmo di ricerca, usi un dataset di prova che contiene solo testo con 3 lettere minuscole:
a, b e c.
Nel database ci sono
n stringhe, e hai a disposizione k query. Vuoi che il motore di ricerca sia sia performante sia tollerante agli errori, quindi hai deciso di consentire al massimo 1 lettera errata.Per ogni stringa di query, il programma deve controllare se la stringa è presente nel database consentendo al massimo un carattere errato (senza aggiungere o rimuovere caratteri).
Input
La prima riga dell’input contiene un singolo intero
n (1 ≤ n ≤ 100 000).Le successive
n righe contengono le stringhe presenti nel database . È garantito che la somma delle lunghezze delle stringhe nel database non superi 100 000.La prima riga dell’input contiene un singolo intero
k (1 ≤ k ≤ 100 000), il numero di query.Le successive
k righe contengono le stringhe di query . È garantito che la somma delle lunghezze delle stringhe di query non superi 100 000.Output
Per ognuna delle stringhe di query, il programma deve stampare
Yes se essa esiste nel database, altrimenti No, consentendo al massimo una lettera errata.Esempi
Input | Output |
2
aaabccc
aaaaaac
4
aaabccc
aabaccc
aaaaaab
aaaaaaaab | Yes
No
Yes
No |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB