Лексикографически минимальное вращение строки

В информатике лексикографически минимальное вращение строки или лексикографически наименьшая круговая подстрока — это проблема поиска вращения строки, обладающей наименьшим лексикографическим порядком из всех таких вращений. Например, лексикографически минимальной ротацией «bbaaccaadd» будет «aaccaaddbb». Строка может иметь несколько лексикографически минимальных вращений, но для большинства приложений это не имеет значения, поскольку вращения должны быть эквивалентными. Нахождение лексикографически минимального поворота полезно как способ нормализации строк. Если строки представляют собой потенциально изоморфные структуры, такие как графы , нормализация таким способом позволяет легко проверить равенство. ^[1] Распространенный прием реализации при работе с циклическими строками заключается в объединении строки в саму себя вместо выполнения модульной арифметики над строковыми индексами.

Алгоритмы [ править ]

Наивный алгоритм [ править ]

Наивный алгоритм поиска лексикографически минимального поворота строки заключается в переборе последовательных поворотов, отслеживая при этом наиболее лексикографически минимальный поворот. Если строка имеет длину $n$ , этот алгоритм работает за $O (n 2)$ время в худшем случае.

Алгоритм Бута [ править ]

Эффективный алгоритм был предложен Бутом (1980). ^[2] Алгоритм использует модифицированную функцию предварительной обработки из алгоритма поиска строк Кнута-Морриса-Пратта . Функция отказа для строки вычисляется как обычно, но строка вращается во время вычисления, поэтому некоторые индексы должны вычисляться более одного раза по мере их обхода. Как только все индексы функции отказа были успешно вычислены без повторного вращения строки, известно, что минимальное лексикографическое вращение найдено, и возвращается его начальный индекс. Корректность алгоритма несколько сложно понять, но его легко реализовать.

def least_rotation(s: str) -> int:
    """Booth's lexicographically minimal string rotation algorithm."""
    n = len(s)
    f = [-1] * (2 * n)
    k = 0
    for j in range(1, 2 * n):
        i = f[j - k - 1]
        while i != -1 and s[j % n] != s[(k + i + 1) % n]:
            if s[j % n] < s[(k + i + 1) % n]:
                k = j - i - 1
            i = f[i]
        if i == -1 and s[j % n] != s[(k + i + 1) % n]:
            if s[j % n] < s[(k + i + 1) % n]:
                k = j
            f[j - k] = -1
        else:
            f[j - k] = i + 1
    return k

Интересно то, что удаление всех строк кода, которые изменяют значение $k,$ приводит к исходной функции предварительной обработки Кнута-Морриса-Пратта, поскольку $k$ (представляющий вращение) останется нулевым. Алгоритм Бута работает в ⁠ $O(n)$ ⁠ время, где $n$ — длина строки. Алгоритм работает не более ⁠ $3n$ ⁠ сравнения в худшем случае и требуют дополнительной памяти длиной $n$ для хранения таблицы функций отказа.

Шилоаха канонизации Алгоритм быстрой

Шайло (1981) ^[3] предложил алгоритм, улучшающий результат Бута с точки зрения производительности. Было замечено, что если существует $q$ эквивалентных лексикографически минимальных вращений строки длины $n$ , то строка должна состоять из $q$ равных подстрок длины ⁠ $d=n/q$ ⁠ . Алгоритму требуется всего ⁠ $n+d/2$ ⁠ сравнения и константное пространство в худшем случае.

Алгоритм разделен на два этапа. Первая фаза представляет собой быстрое сито, которое исключает индексы, которые явно не являются отправными точками для лексикографически минимальной ротации. Затем вторая фаза находит лексикографически минимальный индекс начала вращения из оставшихся индексов.

Линдону факторизации Дюваля по Алгоритм

Дюваль (1983) ^[4] предложил эффективный алгоритм, включающий факторизацию строки на составляющие ее слова Линдона , который работает за линейное время с постоянными требованиями к памяти.

Варианты [ править ]

Шайло (1979) ^[5] предложил алгоритм для эффективного сравнения двух круговых строк на предмет равенства без требования нормализации. Дополнительным применением алгоритма является быстрое создание определенных химических структур без повторений.

См. также [ править ]

Ссылки [ править ]

^ Келлог С. Бут; Колборн, Чарльз Дж . (1980). «Алгоритмы автоморфизма линейного времени для деревьев, интервальных графов и плоских графов» . SIAM Journal по вычислительной технике . 10 (1). Общество промышленной и прикладной математики: 203–225. дои : 10.1137/0210015 . ISSN 0097-5397 .
^ Келлог С. Бут (1980). «Лексикографически наименьшие круговые подстроки». Письма об обработке информации . 10 (4–5). Эльзевир: 240–242. дои : 10.1016/0020-0190(80)90149-0 . ISSN 0020-0190 .
^ Йоси Шилоах (1981). «Быстрая канонизация круглых струн». Журнал алгоритмов . 2 (2). Эльзевир: 107–121. дои : 10.1016/0196-6774(81)90013-4 . ISSN 0196-6774 .
^ Жан Пьер Дюваль (1983). «Факторизация слов по упорядоченному алфавиту». Журнал алгоритмов . 8 (8). Эльзевир: 363–381. дои : 10.1016/0196-6774(83)90017-2 . ISSN 0196-6774 .
^ Йоси Шилоах (1979). «Быстрый алгоритм проверки эквивалентности циклических списков». Письма об обработке информации . 8 (5). Эльзевир: 236–238. дои : 10.1016/0020-0190(79)90114-5 . ISSN 0020-0190 .

[1] Келлог С. Бут; Колборн, Чарльз Дж . (1980). «Алгоритмы автоморфизма линейного времени для деревьев, интервальных графов и плоских графов» . SIAM Journal по вычислительной технике . 10 (1). Общество промышленной и прикладной математики: 203–225. дои : 10.1137/0210015 . ISSN 0097-5397 .

[2] Келлог С. Бут (1980). «Лексикографически наименьшие круговые подстроки». Письма об обработке информации . 10 (4–5). Эльзевир: 240–242. дои : 10.1016/0020-0190(80)90149-0 . ISSN 0020-0190 .

[3] Йоси Шилоах (1981). «Быстрая канонизация круглых струн». Журнал алгоритмов . 2 (2). Эльзевир: 107–121. дои : 10.1016/0196-6774(81)90013-4 . ISSN 0196-6774 .

[4] Жан Пьер Дюваль (1983). «Факторизация слов по упорядоченному алфавиту». Журнал алгоритмов . 8 (8). Эльзевир: 363–381. дои : 10.1016/0196-6774(83)90017-2 . ISSN 0196-6774 .

[5] Йоси Шилоах (1979). «Быстрый алгоритм проверки эквивалентности циклических списков». Письма об обработке информации . 8 (5). Эльзевир: 236–238. дои : 10.1016/0020-0190(79)90114-5 . ISSN 0020-0190 .

[1]

[2]

[3]

[4]

[5]