printЗанятие 5 (подготовка к олимпиаде)

printA. Снежный ком

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

Фраза, которая начинается со слова из одной буквы, и в которой каждое слово на одну букву длиннее предыдущего, называется "снежным комом". Вот великолепный пример снежного кома из 20 английских слов: "I do not know where family doctors acquired illegibly perplexing handwriting; nevertheless, extraordinary pharmaceutical intellectuality, counterbalancing indecipherability, transcendentalizes intercommunications' incomprehensibleness."
Для получения случайного осмысленного текста можно использовать следующий алгоритм. Возьмем произвольный большой текст. Взяв в качестве первого слова любое слово из этого текста, следующим ставим слово, которое расположено где-нибудь в исходном тексте непосредственно после выбранного слова. Если есть несколько кандидатов, случайно выбираем любого из них. Аналогично третьим ставим слово, которое расположено в исходном тексте непосредственно после второго выбранного слова. И так далее.
Напишите программу, которая выделяет максимально длинный "снежный ком" из большого текста по указанному выше алгоритму.
Во входном файле содержится одна или более строк длиной не более 200 символов, в которых содержится текст, состоящий не более чем из 30000 слов. Количество различных слов в тесте не превышает 5000. Максимальная длина слов не превышает 20 букв. Текст состоит из латинских букв и знаков препинания. Регистр букв при составлении снежного кома игнорируется. Словом будем называть последовательность прописных и строчных латинских букв ("x-ray" состоит из 2 слов X и RAY, "Mary's" состоит из 2 слов MARY и S, "It's words" состоит из 3 слов IT, S и WORDS).
В выходной файл вывести самый длинный снежный ком, найденный в тексте. Снежный ком не должен содержать знаков препинания, а слова, напечатанные строчными буквами, должны отделяться друг от друга одним пробелом. Если существует несколько подходящих вариантов, вывести один (любой) из них.

Пример ввода

Where family doctors study? I do not know where.
Doctors acquired illegibly drugs from gypsies.
You received F mark for illegibly perplexing handwriting.

Вывод для примера

i do not know where family doctors acquired illegibly perplexing handwriting
loading