Решение задачи A-функция от строчки с Яндекс Контест

Без пояснения   Просмотров: 1864

Дана строка 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 = int(input())
s = input()
s = s + s[::-1]
n = len(s)
z = n * [0]
bigg = 10 ** 9
l, r = 0, 0
for i in range(n):
    if bigg >= 0:
        d = 0
    if i <= r:
        d = z[i - l]
        if i + d - 1 < r:
            z[i] = d
            bigg = 0
            continue
        else:
            d = r - i + 1
    while i + d < n and s[d] == s[i + d]:
        d += 1
    z[i] = d
    l, r = i, i + d - 1
# print(z)
for i in range(len(z) - 1, n//2 - 1, -1):
    print(z[i], end=" ")

         

Администратор Photo Автор: Администратор



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться



info@mycod.net   Карта сайта   Правообладателям
Заявка на расчет
×

или напишите нам прямо сейчас:

Написать в MAX
Написать в Telegram
Написать в WhatsApp