Подразделы

Другие разделы

Дата и время

20/12/2024 15:07:18

Авторизация

Неклассифицированные

A Foldy but a Goody Checker Give Me an E Target Practice Агентурная сеть Ленивый папа Последовательность Правописание Прибор Сетки Стрелок Строки Фибоначчи Шутка

Правописание

Ограничения: время – 4s/8s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Вам предлагается написать программу для проверки правописания.

Задан произвольный текст. Слова в этом тексте состоят из больших и маленьких латинских букв, все остальные символы считаются разделителями. При наборе текста в словах иногда возникают ошибки, которые делятся на 4 вида:

замена одной буквы другой (например, cst вместо cat)
дублирование буквы (например, caat вместо cat)
пропуск буквы (например, ct вместо cat)
перестановка двух рядом стоящих букв (например, cta вместо cat)

Примем следующее допущение – будем считать, что при наборе текста в каждом слове может быть допущено не более одной ошибки, которая может быть любой из вышеперечисленных четырёх.

Кроме текста, задан словарь – набор правильно написанных слов.

Ваша программа должна найти слова в исходном тексте, которые отсутствуют в словаре, и предложить варианты правильного написания при их наличии. Регистр символов не учитывается (например, слово cat может быть получено из слова CST одной заменой символа S на a. Однако, обратите внимание, что регистр учитывается при выводе результатов – см. формат выходных данных).

В первой строке входного файла находится целое число `K` (`1\ ≤\ K\ ≤\ 1000`) – количество слов в словаре. В следующих `K` строках располагаются слова словаря в лексикографическом порядке, каждое слово в отдельной строке, длины слов не превышают 20 символов, используются только символы нижнего регистра.

В следующей строке находится целое число `N` (`1\ ≤\ N\ ≤\ 300`) – количество строк текста. В следующих `N` строках располагается текст, каждая строка не превышает 80 символов, все слова в тексте не превышают 20 символов.

В выходной файл для каждого слова в исходном тексте, которое отсутствует в словаре, выведите в отдельной строке через пробел:

слово из исходного текста,
номер строки в исходном тексте и номер слова в этой строке
перечень слов из словаря (в любом порядке), из которых могло бы быть получено данное слово вследствие одной ошибки. Если таких слов нет, выведите “NO VARIANTS”. Если таких слов больше трех, выведите любые три из них, затем многоточие "...".

Слова из исходного текста должны быть выведены в том же регистре, как в исходном тексте. Слова из словаря выводятся в нижнем регистре, как они записаны в словаре.

Строки должны быть выведены в порядке, в котором слова встречаются в исходном тексте.

Пример ввода

12
amount
as
growing
if
in
information
it
number
of
rapidly
the
this
2
Thi amaunt of infomatin
is growin rapidly.

Пример вывода

Thi 1 1 this the
amaunt 1 2 amount
infomatin 1 4 NO VARIANTS
is 2 1 as in it...
growin 2 2 growing

Источник: VII межвузовская олимпиада по программированию Вологда, 2004