Плюсануть
Поделиться
Класснуть
Запинить


Олимпиадный тренинг

Вы можете самостоятельно решать эти задачи столько раз, сколько вам это понадобится.
   

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

Z-функция. Префикс-функция

В теории кодирования часто используют беспрефиксные коды наборы слов, ни одно из которых не является префиксом (Слово α называется префиксом слова β, если α получается из β удалением нуля или более символов в конце. Например, слова, a, ab и aba являются префиксами слова aba) другого. Например, набор слов aba, aa и bac является беспрефиксным кодом, а набор abac, aba, ba нет, поскольку слово aba является префиксом слова abac.
 
Профессор Дешифро работает в лаборатории исследования бесполезной информации и изучает свое новое изобретение почти беспрефиксные коды. Набор слов называется почти беспрефиксным кодом уровня k, если наибольший общий префикс двух любых слов из набора не превышает по длине k. Например, набор abac, abс, ba является почти беспрефиксным кодом уровня 2, а набор abac , abab, ba нет, поскольку наибольший общий префикс слов abac и abab имеет длину 3.
 
Очередная задача, которую профессор Дешифро поставил своим лаборантам, заключается в следующем: по заданному набору слов и числу k требуется выбрать из заданных слов максимальный набор, который является почти беспрефиксным кодом уровня k. Вам, как младшему лаборанту, поручили написать соответствующую программу.
 
Входные данные
Первая строка входного файла содержит два целых числа: n и k количество слов в заданном наборе и уровень почти беспрефиксного кода, который требуется построить (1 ≤ n ≤ 100000, 0 ≤ k ≤ 200). Следующие n строк содержат по одному слову. Слова состоят из строчных букв латинского алфавита. Длина каждого слова от 1 до 200 символов. Суммарная длина всех слов не превышает 106. Все слова различны.
 
Выходные данные
Выведите одно число m - максимальное количество слов, которые можно выбрать из заданного набора, чтобы они образовывали почти беспрефиксный код уровня k. 
Ввод Вывод
6 2
aba
bacaba
abacaba
baca
abac
caba
3

Префикс-функция

Z-функция. Префикс-функция

Дана непустая строка S, длина которой N не превышает 106. Будем считать, что элементы строки нумеруются от 1 до N.
 
Для каждой позиции i символа в строке нас будет интересовать подстрока, заканчивающаяся в этой позиции, и совпадающая с некоторым началом всей строки. Вообще говоря, таких подстрок будет несколько, не меньше двух. Самая длинная из них имеет длину i, она нас интересовать не будет. А будет нас интересовать самая длинная из остальных таких подстрок (заметим, что такая подстрока всегда существует — в крайнем случае, если ничего больше не найдется, сгодится пустая подстрока).
 
Значением префикс-функции π[i] будем считать длину этой подстроки.
 
Префикс-функция используется в различных алгоритмах обработки строк. В частности, с её помощью можно быстро решать задачу о поиске вхождения одной строки в другую («поиск образца в тексте»).
 
Требуется для всех i от 1 до N вычислить π[i].
 
Входные данные
Одна строка длины N, 0 < N ≤ 106, состоящая из маленьких латинских букв.
 
Выходные данные
Выведите N чисел — значения префикс-функции для каждой позиции, разделенные пробелом.

Ввод Вывод
abracadabra 0 0 0 1 0 1 0 1 2 3 4