Fuzzy Matching (Correspondance approximative)
Imaginez que vous soyez l’un des tout premiers ingénieurs chez Google, et que vous deviez implémenter une fonctionnalité dans Google Search pour vérifier si la requête utilisateur est ou non présente dans la base de données.
Comme vous venez juste de commencer à travailler sur l’algorithme de recherche, vous testez un jeu de données minimal qui ne contient que du texte composé des 3 lettres minuscules
a, b et c.
Il y a
n chaînes de caractères dans la base de données et vous recevez k requêtes. Vous voulez rendre le moteur de recherche à la fois performant et tolérant aux erreurs, c’est pourquoi vous avez décidé d’autoriser au maximum une seule lettre mal orthographiée.Pour chaque chaîne de requête, le programme doit vérifier si la requête est bien présente dans la base de données, en tolérant au plus un caractère erroné (sans ajout ni suppression).
Entrée
La première ligne de l’entrée contient un entier
n (1 ≤ n ≤ 100 000).Les
n lignes suivantes contiennent les chaînes de la base de données . Il est garanti que la somme des longueurs de ces chaînes ne dépasse pas 100 000.La première ligne de l’entrée contient ensuite un entier
k (1 ≤ k ≤ 100 000), qui est le nombre de requêtes.Les
k lignes suivantes contiennent les chaînes de requête . Il est garanti que la somme des longueurs de ces requêtes ne dépasse pas 100 000.Sortie
Pour chacune des chaînes de requête, le programme doit afficher
Yes si elle est présente dans la base de données et No sinon, en autorisant au plus une lettre erronée.Exemples
Entrée | Sortie |
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