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