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