- Описание
- Отправленные решения
473. Как курица лапой
Программист Никита увлекается генеалогией и часто сталкивается с тем, что в старинных метрических книгах записи сложно разобрать из-за неразборчивого почерка или выцветших чернил. Он решил написать приложение, которое позволяет сканировать и распознавать такие записи. Из-за большого количества других проектов у Никиты не хватает времени довести работу до конца, и он просит вас помочь с одной подзадачей. Сканер, который он написал, очень неточный и часто делает ошибки в распознанных словах. Вам нужно подобрать наиболее вероятное слово исходя из результата, выданного сканером. Известно, что если не существует слова, которое выдал сканер, то где-то закралась ошибка. Возможно, что даже не одна. Никита сказал, что при ошибке сканер с вероятностью поставил не ту букву, с вероятностью пропустил букву и с вероятностью добавил лишнюю. Чтобы не выдавать совсем уж разные названия, будем считать, что слова, похожие с вероятностью , нельзя выдавать как ответ.
Формат ввода
В первой строке входных данных находится длина строки, полученной от сканера, , а в следующей — она сама.
В третьей строке следует размер словаря 1 .
В следующих строках следует словарь.
В нечётных строках содержатся длины строк из словаря , а в чётных — сами строки.
Все слова во входных данных состоят из строчных латинских букв.
Формат вывода
В единственной строке выходных данных должно находиться наиболее вероятное слово или NO MATCH, если таковых нет. Если наиболее вероятными являются несколько слов, то необходимо вывести минимальное лексикографически.
Ограничения
Ограничение времени
1 с
Ограничение памяти
64 МБ
Пример 1
3
abc
3
3
pac
2
ab
4
abcd
ab
Пример 2
5
abcde
3
5
amntp
2
ce
6
abacde
abacde
Пример 3
4
robn
4
4
robp
3
obn
5
robna
4
robn
robn