Дана непустая строка S длиной N символов. Будем считать, что элементы строки нумеруются от 1 до N.
Для каждой i-й позиции строки S определим подстроку, заканчивающуюся в этой позиции, которая совпадает с некоторым началом всей строки S и имеет длину, меньшую, чем i (т.е. не равна i-му префиксу исходной строки). Значением префикс-функции P(i) будем считать длину этой подстроки.
Требуется для всех i от 1 до N вычислить значение P(i).
В единственной строке входного файла INPUT.TXT записана строка, состоящая из символов с кодами ASCII от 33 до 127. Длина строки не превышает 106.
В выходной файл OUTPUT.TXT выведите все значения префикс-функции.
№ | INPUT.TXT | OUTPUT.TXT |
1 | ABRACADABRA | 0 0 0 1 0 1 0 1 2 3 4 |
2 | ABACABADABACABA | 0 0 1 0 1 2 3 0 1 2 3 4 5 6 7 |