АВТ
Язык:

Дистанционный практикум по программированию

Задачи Online статус Турниры
Учебники Справка СДО
 
Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь.

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

Ограничение времени: 3 сек.
Ограничение памяти:65536 КБайт
Баллы:100
Статистика Послать на проверку Задачу добавил debug

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

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

·        замена одной буквы другой (например, cst вместо cat)

·        дублирование буквы (например, caat вместо cat)

·        пропуск буквы (например, ct вместо cat)

·        перестановка двух рядом стоящих букв (например, cta вместо cat)

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

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

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

 

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

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

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

·        слово из исходного текста,

·        номер строки в исходном тексте и номер слова в этой строке

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

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

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

Пример

STDIN

STDOUT

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 /
84. E - Лексикографический порядок 85. 86. G - Строки Фибоначчи 87. H - Прибор 88. I - Скобки
 
время генерации 0.235 сек.
© Copyright ВоГУ, АВТ, Носов Д.А., Андрианов И.А.