Декомпозиция Линдона и минимальный циклический сдвиг

Коротко

Слово Линдона

Строка называется простым словом (словом Линдона), если она строго меньше всех своих собственных суффиксов.

'a'      — простое
'ab'     — простое ('ab' < 'b')
'aab'    — простое ('aab' < 'ab' < 'b')
'ba'     — НЕ простое ('a' < 'ba')
'abab'   — НЕ простое ('ab' < 'abab')

Эквивалентное определение: строка строго меньше всех своих нетривиальных циклических сдвигов.

Теорема о декомпозиции

Любая строка единственным образом разбивается на конкатенацию простых слов, идущих в невозрастающем порядке:

s = w₁ w₂ ... wₖ,  где w₁ ≥ w₂ ≥ ... ≥ wₖ

Примеры:

'abacaba'  →  'abac' + 'ab' + 'a'
'aabaab'   →  'aabaab'          (вся строка простая)
'cba'      →  'c' + 'b' + 'a'

Единственность разложения — сильное свойство, на котором строятся дальнейшие применения.

Алгоритм Дюваля

Находит декомпозицию за O(n) времени и O(1) дополнительной памяти. Работает с тремя указателями.

def duval(s: str) -> list[str]:
    n = len(s)
    result = []
    i = 0

    while i < n:
        j, k = i + 1, i

        # ищем период текущего кандидата
        while j < n and s[k] <= s[j]:
            if s[k] < s[j]:
                k = i          # нашли больший символ — период сбрасывается
            else:
                k += 1         # символы равны — период продолжается
            j += 1

        # длина простого слова
        period = j - k
        while i <= k:
            result.append(s[i:i + period])
            i += period

    return result


print(duval('abacaba'))   # ['abac', 'ab', 'a']
print(duval('aabaab'))    # ['aabaab']
print(duval('cba'))       # ['c', 'b', 'a']

Логика: i — начало текущего простого слова, k и j сравнивают строку с её сдвигом на j - k. Когда сравнение нарушается, мы знаем длину периода и можем «отрезать» одно или несколько повторений.

Алгоритм линейный, потому что j только растёт.

Минимальный циклический сдвиг

Классическое применение. Задача: найти такой поворот строки, который лексикографически наименьший.

'bbaa'  →  сдвиги: bbaa, baab, aabb, abba
           минимальный: 'aabb'

Наивно — сгенерировать все n сдвигов и сравнить, O(n²). Через декомпозицию Линдона — O(n).

Приём: удваиваем строку и ищем начало простого слова, которое начинается в первой половине и достаточно длинное.

def min_cyclic_shift(s: str) -> str:
    doubled = s + s
    n = len(doubled)
    i, best = 0, 0

    while i < len(s):
        best = i
        j, k = i + 1, i

        while j < n and doubled[k] <= doubled[j]:
            if doubled[k] < doubled[j]:
                k = i
            else:
                k += 1
            j += 1

        while i <= k:
            i += j - k

    return doubled[best:best + len(s)]


print(min_cyclic_shift('bbaa'))      # 'aabb'
print(min_cyclic_shift('abacaba'))   # 'aabacab'
print(min_cyclic_shift('aaa'))       # 'aaa'

Обратите внимание: best обновляется в начале каждой итерации внешнего цикла, и в конце содержит начало последнего рассмотренного блока — это и есть искомая позиция.

Где применяется

Канонизация циклических объектов. Ожерелья, кольцевые последовательности, циклические ДНК-последовательности приводятся к единому представлению — минимальному сдвигу. После этого их можно сравнивать напрямую или класть в хеш-таблицу.

Сравнение молекул в химинформатике: кольцевые структуры нормализуются одинаково.

Дедупликация циклических данных.

Генерация ожерелий — все простые слова заданной длины в лексикографическом порядке (алгоритм FKM строится на той же теории).

Суффиксные структуры. Декомпозиция Линдона используется в некоторых алгоритмах построения суффиксных массивов.

Альтернатива: алгоритм Бута

Ту же задачу минимального сдвига решает алгоритм Бута, основанный на префикс-функции KMP. Сложность та же O(n), но константа обычно чуть хуже, а код длиннее. Дюваль считается более практичным.

Частые ошибки

Сравнение < вместо <= в условии цикла. Ломает обработку равных символов и приводит к неверному разбиению.

Сброс k в неправильное значение. При строгом неравенстве k должен возвращаться именно к i, а не к предыдущему значению.

Забытое удвоение строки при поиске циклического сдвига. Без него алгоритм не увидит сдвиги, «переходящие через край».

Внешний цикл до 2n вместо n. При удвоенной строке достаточно пройти первую половину.

Что запомнить

• Слово Линдона строго меньше всех своих суффиксов и циклических сдвигов.
• Любая строка единственным образом раскладывается на невозрастающую последовательность простых слов.
• Алгоритм Дюваля находит разложение за O(n) времени и O(1) памяти.
• Минимальный циклический сдвиг ищется тем же алгоритмом по удвоенной строке.
• Основное применение — канонизация циклических последовательностей.

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→