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. Вам, как младшему лаборанту, поручили написать соответствующую программу.

Примеры

Примеры

#include <bits/stdc++.h>
main()
{
    std::string s;
    std::cin >> s;
    int n = s.size(), p[50003], j, i = 1;
    for (; i < n; i++)
    {
        j = p[i - 1];
        for (; j && s[i] != s[j]; j = p[j - 1]);
        p[i] = (s[i] == s[j] ? ++j : j);
    }
    std::cout << n - p[n - 1];
}

Корвину удалось перехватить n сообщений о перемещении войск Эрика. Правда, они оказались зашифрованными, но это не беда! Вы ведь поможете ему расшифровать эти сообщения? Это должно быть не сложно, ибо Корвин знает хотя бы одну подстроку в каждом исходном сообщении.

Известно, что для шифровки Эрик использует шифр Цезаря, то есть шифр, в котором буква с номером i заменяется на букву с номером i + k, где k - некоторое число.

Так как современные компиляторы не поддерживают амберский алфавит, мы будем заменять символы на их порядковый номер - число от 1 до q, где q - количество символов в алфавите.

Каждое сообщение имеет длину x, а каждая известная подстрока его расшифровки - y.

Ваша цель - восстановить все изначальные сообщения.

Примеры