Московская городская олимпиада школьников по информатике,
2005/06 учебный год
при поддержке компании
Задача H. Функция A от строчки
| Имя входного файла: | h.in |
| Имя выходного файла: | h.out |
| Максимальное время работы на одном тесте: | 1 секунда |
| Максимальный объем используемой памяти: | 64 мегабайта |
Дана строка 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).
Пример
| h.in | h.out |
5 aabaa |
1 2 0 1 5 |