@tazhimbetov
Программист 1 курс

Что делает этот код?

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

Это код на codeforces.com/problemset/problem/126/B на эту задачу, объясните пожалуйста как он работает
  • Вопрос задан
  • 151 просмотр
Решения вопроса 1
  • longclaps
    @longclaps
    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")
    Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через TM ID
Похожие вопросы