АВТ
Язык:

Дистанционный практикум по программированию

Задачи Online статус Турниры
Учебники Справка СДО
 
Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь.

1855. Поисковый индекс

Ограничение времени: 6 сек.
Ограничение памяти:1048576 КБайт
Баллы:100
Статистика Послать на проверку Задачу добавил debug

Аспирантка Анна занимается разработкой нового метода индексирования для ускорения нечёткого поиска. Анна решила, что множество ключей её индекса будет определяться следующим образом.

Пусть имеется набор из N входных текстовых документов. Назовём непустую строку полезной, если она имеет длину не более L и встречается в качестве подстроки не менее чем в одном и не более чем в T документах. Тогда множество ключей индекса строится так:

  • На первом шаге включим в результирующее множество все полезные строки.
  • На втором шаге удалим из ответа лишние элементы, пользуясь следующим правилом: если в множестве присутствуют два элемента s1 и s2, такие что s1 является подстрокой s2, то элемент s2 удаляется.

Рассмотрим пример. Пусть дано три входных документа – 'aba', 'caba' и 'dab', при этом T = 2 и L = 3.

После первого шага получаем множество 'aba', 'ba', 'c', 'ca', 'cab', 'd', 'da', 'dab'. Подстроки 'a' и 'b' в него не попали, так как встречаются более чем в T документах. После удаления лишних элементов на втором шаге окончательный ответ будет равен 'ba', 'c', 'd'

Анна заметила, что построение индекса непосредственно вышеописанным способом может выполняться слишком долго. Ваша задача – придумать и реализовать эффективный алгоритм построения результирующего множества.

Входные данные

В первой строке входных данных записаны три натуральных числа N, T и L (1 ≤ N, T ≤ 106, 1 ≤ L ≤ 10).

Далее идут N входных документов – непустых строк, содержащих только строчные английские буквы. Сумма длин всех строк не превышает 106.

Выходные данные

Выведите элементы результирующего множества в лексикографическом порядке

Примеры

Входные данные
3 2 3
aba
caba
dab
Выходные данные
ba
c
d
Входные данные
2 1 5
aaaaaaaa
aaaaaaaa
Выходные данные
Входные данные
2 1 5
aaaaaaca
aaaaaaab
Выходные данные
b
c

Условия всех задач турнира (pdf)


Статистика Послать на проверку Обсуждение задачи Автор/источник:
Задачи с соревнований / Межвузовские олимпиады / XXI межвузовская олимпиада /
1854. I - Гири 1855.
 
время генерации 0.078 сек.
© Copyright ВоГУ, АВТ, Носов Д.А., Андрианов И.А.