C. Конкатенация
Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Рассмотрим две строки α и β. Их конкатенацией называется строка, получающаяся в результате приписывания к строке α строки β. Эта строка обозначается αβ. Например, конкатенацией строк 'ab' и 'ac' будет строка 'abac'. Очевидно, что это определение естественным образом распространяется на конкатенацию произвольного количества строк. Так, конкатенацией нуля строк будет пустая строка, а конкатенацией одной строки будет она сама.
Рассмотрим некоторое множество W, состоящее из строк. Назовём его замыканием множество W^{*}, состоящее из тех и только тех строк, которые можно получить в результате конкатенации нуля и более строк из множества W. Таким образом, множество W^{*} содержит пустую строку, и если строка α принадлежит множеству W^{*}, а строка β принадлежит множеству W, то
строка αβ принадлежит множеству W^{*}. Более того, все элементы множества W^{*} можно представить в таком виде, то есть W^{*} является пересечением всех множеств с указанными выше свойствами. Например, если W={a,ab}, то W^{*} состоит из всех строк, в которых перед каждой буквой 'b' идёт хотя бы одна буква 'a'.
Задано некоторое множество строк W. Требуется найти
множество X, такое, что W^{*}=X^{*} и множество X имеет минимальное возможное число элементов. В случае, если таких множеств несколько, подходит любое из них. Например, если W={a,aabb,ab,ac,b,bac}, то единственным множеством, удовлетворяющим условиям задачи будет множество {a,ac,b}.
Ввод состоит из набора строк, каждая из которых является
элементом множества W. Каждая строка из множества W встречается во входном файле хотя бы один раз. Суммарная длина всех строк во входном файле не превосходит 10^4. Количество строк во входном файле не превосходит 10^4. После каждой строки из множества W во входном файле идёт перевод строки (пара символов с ASCII кодами 13 и 10). Строки состоят из символов с ASCII кодами от 33 до 126 включительно.
Выведите элементы одного из множеств X,
удовлетворяющих условиям задачи. Каждая строка множества X
должна быть выведена ровно один раз. Строки должны идти в
лексикографическом порядке (лексикографический порядок
используется в словарях, в этом порядке строка 'ab' меньше строки 'aba' и строка 'ab' меньше строки 'ac'). После каждой
строки множества X должен идти один перевод строки.
Пример ввода
a
aabb
ab
ac
b
bac
Источник: XI командный чемпионат школьников Санкт-Петербурга по программированию