Задача №1042. A-функция от строчки
Дана строка 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.
Входные данные
В первой строке входного файла записано одно число N. 1≤N≤200000. Во второй строке записана строка длиной N символов, состоящая только из больших и/или маленьких латинских букв.
Выходные данные
В выходной файл выведите N чисел — значения функции A(1), A(2), … A(N).
Примеры
Входные данные
5 aabaa
Выходные данные
1 2 0 1 5
Сдать: для сдачи задач необходимо войти в систему