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

Задача . Префикс-функция


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

 

Примеры
Входные данные Выходные данные
1 abracadabra 0 0 0 1 0 1 0 1 2 3 4



time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w6442
Комментарий учителя