eolymp
bolt
Try our new interface for solving problems
Məsələlər

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

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

Zaman məhdudiyyəti 2 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB

В теории кодирования часто используют беспрефиксные коды - наборы слов, ни одно из которых не является префиксом другого. Например, набор слов "aba", "aa" и "bac" является беспрефиксным кодом, а набор "abac", "aba", "ba" - нет, поскольку слово "aba" является префиксом слова "abac".

Профессор Дешифро работает в лаборатории исследования бесполезной информации и изучает свое новое изобретение - почти беспрефиксные коды. Набор слов называется почти беспрефиксным кодом уровня k, если наибольший общий префикс двух любых слов из набора не превышает по длине k. Например, набор "abac", "abс", "ba" является почти беспрефиксным кодом уровня 2, а набор "abac", "abab", "ba" - нет, поскольку наибольший общий префикс слов "abac" и "abab" имеет длину 3.

Очередная задача, которую профессор Дешифро поставил своим лаборантам, заключается в следующем: по заданному набору слов и числу k требуется выбрать из заданных слов максимальный набор, который является почти беспрефиксным кодом уровня k. Вам, как младшему лаборанту, поручили написать соответствующую программу.

Giriş verilənləri

Первая строка входного файла содержит два целых числа: n и k - количество слов в заданном наборе и уровень почти беспрефиксного кода, который требуется построить (1n100000, 0k200). Следующие n строк содержат по одному слову. Слова состоят из строчных букв латинского алфавита. Длина каждого слова от 1 до 200 символов. Суммарная длина всех слов не превышает 10^6. Все слова различны.

Çıxış verilənləri

На первой строке выходного файла выведите одно число m - максимальное количество слов, которые можно выбрать из заданного набора, чтобы они образовывали почти беспрефиксный код уровня k. Следующие m строк должны содержать выбранные слова.

Nümunə

Giriş verilənləri #1
6 2
aba
bacaba
abacaba
baca
abac
caba
Çıxış verilənləri #1
3
aba
bacaba
caba