E
E
Elnur Tazhimbetov2018-02-04 19:48:15
Python
Elnur Tazhimbetov, 2018-02-04 19:48:15

What does this code do?

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 the question

In order to leave comments, you need to log in

1 answer(s)
L
longclaps, 2018-02-04
@tazhimbetov

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")

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question