A-функция от строчки
(Время: 1 сек. Память: 16 Мб Сложность: 59%)
Дана строка S, состоящая из N символов. Определим функцию A(i) от первых i символов этой строки следующим образом:
A(i) = максимально возможному k, что равны следующие строки:
S[1]+S[2]+S[3]+…+S[k]
S[i]+S[i–1]+S[i–2]+…+S[i–k+1]
где S[i] – i-ый символ строки S, а знак + означает, что символы записываются в строчку непосредственно друг за другом.
Напишите программу, которая вычислит значения функции A для заданной строчки для всех возможных значений i от 1 до N.
Входные данные
В первой строке входного файла INPUT.TXT записано одно число N. 1 ≤ N ≤ 200000. Во второй строке записана строка длиной N символов, состоящая только из больших и/или маленьких английских букв.
Выходные данные
В выходной файл OUTPUT.TXT выведите N чисел — значения функции A(1), A(2), … A(N).
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 5
aabaa | 1 2 0 1 5 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
