eolymp
bolt
Try our new interface for solving problems
Problems

Почти беспрефиксные коды

Почти беспрефиксные коды

В теории кодирования часто используют беспрефиксные коды - наборы слов, ни одно из которых не является префиксом другого. Например, набор слов "\textbf{aba}", "\textbf{aa}" и "\textbf{bac}" является беспрефиксным кодом, а набор "\textbf{abac}", "\textbf{aba}", "\textbf{ba}" - нет, поскольку слово "\textbf{aba}" является префиксом слова "\textbf{abac}". Профессор Дешифро работает в лаборатории исследования бесполезной информации и изучает свое новое изобретение - почти беспрефиксные коды. Набор слов называется почти беспрефиксным кодом уровня \textbf{k}, если наибольший общий префикс двух любых слов из набора не превышает по длине \textbf{k}. Например, набор "\textbf{abac}", "\textbf{abс}", "\textbf{ba}" является почти беспрефиксным кодом уровня \textbf{2}, а набор "\textbf{abac}", "\textbf{abab}", "\textbf{ba}" - нет, поскольку наибольший общий префикс слов "\textbf{abac}" и "\textbf{abab}" имеет длину \textbf{3}. Очередная задача, которую профессор Дешифро поставил своим лаборантам, заключается в следующем: по заданному набору слов и числу \textbf{k} требуется выбрать из заданных слов максимальный набор, который является почти беспрефиксным кодом уровня \textbf{k}. Вам, как младшему лаборанту, поручили написать соответствующую программу. \InputFile Первая строка входного файла содержит два целых числа: \textbf{n} и \textbf{k} - количество слов в заданном наборе и уровень почти беспрефиксного кода, который требуется построить (\textbf{1} ≤ \textbf{n} ≤ \textbf{100000}, \textbf{0} ≤ \textbf{k} ≤ \textbf{200}). Следующие \textbf{n} строк содержат по одному слову. Слова состоят из строчных букв латинского алфавита. Длина каждого слова от \textbf{1} до \textbf{200 }символов. Суммарная длина всех слов не превышает \textbf{10^6}. Все слова различны. \OutputFile На первой строке выходного файла выведите одно число \textbf{m} - максимальное количество слов, которые можно выбрать из заданного набора, чтобы они образовывали почти беспрефиксный код уровня \textbf{k}. Следующие \textbf{m} строк должны содержать выбранные слова.
Time limit 2 seconds
Memory limit 256 MiB
Input example #1
6 2
aba
bacaba
abacaba
baca
abac
caba
Output example #1
3
aba
bacaba
caba