Fuzzy Matching
Stellen Sie sich vor, Sie wären einer der ersten Ingenieurinnen oder Ingenieure bei Google und müssten eine Funktion in Google Search entwickeln, die überprüft, ob eine Benutzereingabe in der Datenbank vorhanden ist oder nicht.
Da Sie gerade erst mit der Umsetzung des Suchalgorithmus beginnen, testen Sie ihn mit einem Datensatz, der nur Texte aus den drei Kleinbuchstaben
a, b und c enthält.
Es gibt
n Strings in der Datenbank, und Ihnen liegen k Suchanfragen vor. Sie möchten die Suchmaschine sowohl performant als auch fehlertolerant gestalten, daher erlauben Sie bis zu einen falsch geschriebenen Buchstaben.Für jede Suchanfrage soll das Programm prüfen, ob der Suchstring in der Datenbank existiert, wobei bis zu ein falsch geschriebener Buchstabe (ohne Hinzufügen oder Entfernen von Zeichen) zugelassen ist.
Input
Die erste Zeile der Eingabe enthält eine einzelne ganze Zahl
n (1 ≤ n ≤ 100 000).In den nächsten
n Zeilen stehen die Strings der Datenbank . Es ist garantiert, dass die Gesamtlänge aller Strings in der Datenbank 100 000 nicht überschreitet.Danach folgt eine Zeile mit einer einzelnen ganzen Zahl
k (1 ≤ k ≤ 100 000), die die Anzahl der Suchanfragen angibt.In den folgenden
k Zeilen stehen die Suchstrings . Auch hier ist garantiert, dass die Gesamtlänge aller Suchstrings 100 000 nicht überschreitet.Output
Für jeden der Suchstrings soll das Programm
Yes ausgeben, wenn er (unter Zulassung eines einzelnen Tippfehlers) in der Datenbank vorhanden ist, andernfalls No.Examples
Eingabe | Ausgabe |
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