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).
Информация о задаче
Лимит времени: 1 секундаЛимит памяти: 64 MB
Баллы за пройденный тест: 4.54545
Сложность: 40% 12/20
Пример
Пример входных данных5 aabaa |
Пример выходных данных1 2 0 1 5 |
| ← Игра | Список задач | Цирковое шоу → |