Олимпиадный тренинг

Задача . C. Уотто и механизм


Задача

Темы: Бинарный поиск Строки строковые суфф. структуры Структуры данных хэши *2000

Недавно Уотто, хозяину магазина запчастей, поступил заказ на механизм, умеющий обрабатывать строки определённым образом. Изначально в память механизма загружаются n строк. Затем, механизм должен уметь отвечать на запросы следующего вида: «По данной строке s определить, есть ли в памяти механизма строка t, состоящая из того же количества символов, что и s, и отличающаяся от s ровно в одной позиции».

Уотто уже собрал механизм, осталось только написать для него программу и проверить её корректность на данных n исходных строк и m запросах. Эту работу он решил поручить Вам.

Входные данные

В первой строке записано два целых неотрицательных числа n и m (0 ≤ n ≤ 3·105, 0 ≤ m ≤ 3·105) — количество исходных строк и количество запросов соответственно.

Далее следуют n непустых строк, загружаемых в память механизма.

Далее следуют m непустых строк, являющихся запросами к механизму.

Суммарная длина строк во вводе не превышает 6·105. Каждая строка состоит только из букв 'a', 'b', 'c'.

Выходные данные

На каждый запрос выведите в отдельной строке «YES» (без кавычек), если в памяти механизма есть нужная строка, иначе выведите «NO» (без кавычек).


Примеры
№Входные данныеВыходные данные
1 2 3
aaaaa
acacaca
aabaa
ccacacc
caaac 
YES
NO
NO

time 3000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w644
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет