АВТ
Language: Russian
English

Remote Training on Programming

Problems Online status Contests
Textbooks FAQ E-learning
For authors:
Register  ||  Login
 
Hello, Guest! Please login or register.

85. SpellChecking

Time Limit: 3 seconds
Memory Limit:65536KB
Points:100
View Problem Statistics Submit Problem added 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

 

 


View Problem Statistics Submit Problem discussion Author/source:
Problems from Contests / Vologda Students Contests / VII InterUni Contest 2004 /
84. E - Lexicographical order 85. 86. G - Fibonacci Strings 87. H - Device 88. I - Brackerts
time generating 0.344 sec.
© Copyright VSU, AVT, Nosov D.A., Andrianov I.A.