Частотный словарь представляет собой список слов некоторого выбранного языка, каждому из которых ставится в соответствие частота его встречаемости в исходном наборе текстов.
Пусть имеется последовательность слов, состоящих из цифр и букв латинского алфавита.
При этом полагается, что регистр их написания неважен (заглавные и строчные символы эквивалентны между собой).
Все прочие символы, включая пробелы и знаки препинания, играют роль разделителей.
Требуется составить частотный словарь на основе имеющегося текста, определив число вхождений каждого встречаемого в нем слова.
При решении задачи рекомендуется использовать двоичные деревья поиска, списки с пропусками либо хеш-таблицы.
Формат входного файла
Во входном файле "input.txt" содержится исходная последовательность из слов и разделительных символов.
Формат выходного файла
Выходной файл "output.txt" должен содержать все найденные слова (без повторений), приведенные к одному регистру и расположенные в лексикографическом порядке.
Напротив каждого такого слова (через пробел) указывается число его вхождений во входной файл.
Если результирующий словарь оказался пустым, в выходной файл выводится единственный символ пробела.
Ограничения
Полагается, что длина отдельно взятого слова составляет не более 10 символов.
Число уникальных слов, формирующих словарь, не превосходит 5 ⋅ 104.
Размер входного файла не превосходит 10 МБ.
Примеры тестов
№
Входной файл (input.txt)
Выходной файл (output.txt)
1
This is the house that Jack built.
This is the cheese that lay in the house that Jack built.
This is the rat that ate the cheese
That lay in the house that Jack built.
This is the cat that chased the rat
That ate the cheese that lay in the house that Jack built.
This is the dog that worried the cat
That chased the rat that ate the cheese
That lay in the house that Jack built.
This is the cow with the crumpled horn
That tossed the dog that worried the cat
That chased the rat that ate the cheese
That lay in the house that Jack built.
This is the maiden all forlorn
That milked the cow with the crumpled horn
That tossed the dog that worried the cat
That chased the rat that ate the cheese
That lay in the house that Jack built.
This is the man all tattered and torn
That kissed the maiden all forlorn
That milked the cow with the crumpled horn
That tossed the dog that worried the cat
That chased the rat that ate the cheese
That lay in the house that Jack built.
This is the judge all shaven and shorn
That married the man all tattered and torn
That kissed the maiden all forlorn
That milked the cow with the crumpled horn
That tossed the dog that worried the cat
That chased the rat that ate the cheese
That lay in the house that Jack built.
This is the rooster that crowed in the morn
That woke the judge all shaven and shorn
That married the man all tattered and torn
That kissed the maiden all forlorn
That milked the cow with the crumpled horn
That tossed the dog that worried the cat
That chased the rat that ate the cheese
That lay in the house that Jack built.
This is the farmer sowing his corn
That kept the rooster that crowed in the morn
That woke the judge all shaven and shorn
That married the man all tattered and torn
That kissed the maiden all forlorn
That milked the cow with the crumpled horn
That tossed the dog that worried the cat
That chased the rat that ate the cheese
That lay in the house that Jack built.
This is the horse and the hound and the horn
That belonged to the farmer sowing his corn
That kept the rooster that crowed in the morn
That woke the judge all shaven and shorn
That married the man all tattered and torn
That kissed the maiden all forlorn
That milked the cow with the crumpled horn
That tossed the dog that worried the cat
That chased the rat that ate the cheese
That lay in the house that Jack built.
all 15
and 11
ate 10
belonged 1
built 12
cat 9
chased 9
cheese 11
corn 2
cow 7
crowed 3
crumpled 7
dog 8
farmer 2
forlorn 6
his 2
horn 8
horse 1
hound 1
house 12
in 14
is 12
jack 12
judge 4
kept 2
kissed 5
lay 11
maiden 6
man 5
married 4
milked 6
morn 3
rat 10
rooster 3
shaven 4
shorn 4
sowing 2
tattered 5
that 81
the 90
this 12
to 1
torn 5
tossed 7
with 7
woke 3
worried 8
