Решение задачи Z-функция с Codeforces

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

Дана непустая строка S, длина которой N не превышает 106. Будем считать, что элементы строки нумеруются от 0 до N-1.

Требуется для всех i от 0 до N-1 вычислить её z-функцию z[i].

Код 

s = input()
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
for i in range(n):
    print(z[i], end=" ")
d = 0

         

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



Комментарии

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



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

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

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