Remote Training on Programming

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

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

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

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

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

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