What does this code do?

Question

Python

s=input()
j=-1
array = [-1]
for c in s:
    while j != -1 and c != s[j]:
        j = array[j]
    j += 1
    array.append(j)
a = array[-1]
print(a)
if array.count(a) < 2:
    a = array[a]
if a > 0:
    print(s[:a])
else:
    print("Just a legend")

This is the code on codeforces.com/problemset/problem/126/B for this task, please explain how it works

Answer 1

s = "abababa"  # для определённости
j = -1
array = [-1]  # здесь в позиции [i+1] будет длина наибольшего префикса
# который заканчивается буквой по индексу [i]
# (только не префикса, начинающегося с начала строки - 
# а так-то целая строка сама себе префикс, и суффикс, и инфикс)
for i, c in enumerate(s):
    while j != -1 and c != s[j]:
        j = array[j] # вот эта операция равносильна декременту j (для неотрицательных)
        # посмотри на print
    j += 1 # если текущая буква встречается впервые - длина префикса будет 0
    array.append(j)
    print(i, array) # это просто пошаговый вывод

look at this output

0 [-1, 0]
1 [-1, 0, 0]
2 [-1, 0, 0, 1] - вот, по индексу 2 у нас 'a' - с неё и начинается s
вышли из цикла, инкрементировали j
3 [-1, 0, 0, 1, 2] - по индексу 3 у нас 'b' == s[1] - инкрементировали j 
и добавили в хвост
4 [-1, 0, 0, 1, 2, 3]
5 [-1, 0, 0, 1, 2, 3, 4]
6 [-1, 0, 0, 1, 2, 3, 4, 5] - смотри, тут мы много раз подряд 
пролетали мимо тела цикла while, и j росла синхонно с i

ok, what's in the code:

a = array[-1] # это мы получили длину префикса который также и суффикс.
if array.count(a) < 2: # но если столь же длинного инфикса нет -  
    a = array[a] # мы просто прирежем префикс покороче, 
                 # который также является суффиксом, но более коротким
if a > 0:
    print(s[:a])
else:
    print("Just a legend")