Нечеткое сопоставление (Fuzzy Matching)
Представьте, что вы — один из первых инженеров Google, и перед вами стоит задача добавить в Google Search функцию, проверяющую, есть ли введённый пользователем запрос в базе данных.
Поскольку вы только начинаете работу над поисковым алгоритмом, вы тестируете его на небольшом наборе данных, где тексты состоят всего из трёх строчных букв:
a, b и c.
В базе данных хранится
n строк, и вы получаете k запросов. Чтобы сделать поиск и быстрым, и устойчивым к мелким ошибкам, вы решили допускать не более одной неверно набранной буквы.Для каждого строкового запроса программа должна проверить, содержится ли этот запрос в базе с учётом того, что может быть допущена одна ошибка в символе (не добавление или удаление символов, а только замена одного символа).
Входные данные
Первая строка содержит одно целое число
n (1 ≤ n ≤ 100 000).В следующих
n строках даны строки базы данных . Гарантируется, что сумма длин всех строк в базе не превышает 100 000.Далее в первой строке снова задано целое число
k (1 ≤ k ≤ 100 000) — количество запросов.В следующих
k строках даны поисковые строки . Гарантируется, что сумма длин всех поисковых строк не превышает 100 000.Выходные данные
Для каждого запроса выведите
Yes, если такая строка есть в базе (с учётом не более одной ошибочной буквы), и No — в противном случае.Пример
Входные данные | Вывод |
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