20. Исправить все опечатки

Рассмотрим несколько самых популярных ошибок при вводе информации:

• Случайно введена неправильная буква. Слово «метро» может быть введено «меьро».
• Случайно пропущена буква. Слово «метро» может быть введено «мтро».
• Случайно две соседние буквы перепутаны местами. Слово «метро» может быть введено «емтро».

• Случайно добавлена лишняя буква. Слово «метро» может быть введено «метрор».

Вам необходимо скачать архив, в котором находится два файла:

• dictionary.txt – набор слов, которые мы будем считать корректными в данной задаче. Обратите внимание, что в него входят не все слова русского языка.
• queries.txt – набор из 100.000 слов для обработки. Для каждого слова из данного набора следует определить, можно ли, исправив одну или две опечатки, получить слово из словаря.

dictionary.txt (в примере всего три слова в словаре)

яхта
метро
такси

queries.txt (в примере всего четыре слова для обработки)

яхты
емтто
такси
автобус

Для каждого слова сформируйте строку в одном из следующих форматов:

• «слово» 0 – «слово» есть в словаре, т.е. написано без ошибок;
• «слово 1 исправление» -- одну ошибку можно исправить в «слово» и получить «исправление», которое есть в словаре;
• «слово 2 исправление1 исправление2» -- одну ошибку можно исправить в «слово» и получить «исправление1», затем в «исправление1» можно исправить еще одну ошибку и получить «исправление2», которое есть в словаре. Ошибки могут быть разного типа.

• «слово 3+» -- необходимо сделать не менее трех исправлений, чтобы получить какое-то слово из словаря.

answer.txt (пример файла-ответа, может быть любое имя)

яхты 1 яхта
емтто 2 метто метро
такси 0
автобус 3+

Вы должны отправить файл с 100.000 строками. Слова нужно обрабатывать в том порядке, как они идут в файле queries.txt. Кодировка вашего файла должна быть UTF-8.

Решение будет зачтено, если в результирующем файле не менее 99% корректных строк.

Скачать архив.