Суффиксный массив: что это и как построить за O(n log n)

Коротко

Суффиксный массив — отсортированный список всех суффиксов строки. Он решает те же задачи, что суффиксное дерево, но занимает в разы меньше памяти и гораздо проще в реализации.

Что это такое

Возьмём строку banana. Выпишем все её суффиксы с позициями:

0: banana
1: anana
2: nana
3: ana
4: na
5: a

Отсортируем лексикографически:

5: a
3: ana
1: anana
0: banana
4: na
2: nana

Суффиксный массив — это последовательность начальных позиций в отсортированном порядке:

suffix_array = [5, 3, 1, 0, 4, 2]

Сами суффиксы хранить не нужно — их можно восстановить по позиции. Отсюда память O(n) вместо O(n²).

Наивное построение

Прямолинейный способ: сгенерировать все суффиксы и отсортировать.

def suffix_array_naive(s: str) -> list[int]:
    return sorted(range(len(s)), key=lambda i: s[i:])


print(suffix_array_naive('banana'))   # [5, 3, 1, 0, 4, 2]

Одна строка, но сложность O(n² log n): сортировка делает O(n log n) сравнений, каждое сравнение строк стоит до O(n). Для строки в 10⁵ символов не подходит.

Построение удвоением

Основная идея: сортируем суффиксы не целиком, а по первым 2^k символам, удваивая k на каждом шаге.

Ключевой приём — на шаге k мы уже знаем ранги по 2^(k-1) символам. Суффикс длины 2^k — это склейка двух половин длины 2^(k-1), ранги которых известны. Значит сравнение сводится к сравнению пары чисел, а это O(1).

шаг 0: сортируем по 1 символу
шаг 1: сортируем по 2 символам (пара рангов шага 0)
шаг 2: сортируем по 4 символам (пара рангов шага 1)
шаг 3: сортируем по 8 символам
...

Достаточно log n шагов.

def suffix_array(s: str) -> list[int]:
    s += '\x00'           # страж: меньше любого символа
    n = len(s)

    # шаг 0: ранги по одному символу
    sa = sorted(range(n), key=lambda i: s[i])
    rank = [0] * n
    for i in range(1, n):
        rank[sa[i]] = rank[sa[i - 1]] + (s[sa[i]] != s[sa[i - 1]])

    k = 1
    while k < n:
        # ключ суффикса — пара (ранг первой половины, ранг второй)
        def key(i: int) -> tuple:
            second = rank[i + k] if i + k < n else -1
            return (rank[i], second)

        sa = sorted(sa, key=key)

        # пересчитываем ранги по новым ключам
        new_rank = [0] * n
        for i in range(1, n):
            new_rank[sa[i]] = new_rank[sa[i - 1]] + (key(sa[i]) != key(sa[i - 1]))

        rank = new_rank
        if rank[sa[-1]] == n - 1:
            break          # все ранги различны, дальше сортировать нечего

        k *= 2

    return sa[1:]          # отбрасываем страж


print(suffix_array('banana'))   # [5, 3, 1, 0, 4, 2]

Сложность — O(n log² n): log n шагов, на каждом сортировка за O(n log n). Заменив сортировку на поразрядную, получают O(n log n), а алгоритмы вроде SA-IS дают честные O(n).

Страж \x00 нужен, чтобы корректно обрабатывались суффиксы разной длины: символ меньше любого другого гарантирует, что более короткий суффикс окажется раньше при равном префиксе.

Поиск подстроки бинарным поиском

Раз массив отсортирован, вхождения образца ищутся бинарным поиском.

import bisect


def find_occurrences(s: str, sa: list[int], pattern: str) -> list[int]:
    # ищем границы диапазона суффиксов, начинающихся с pattern
    left = bisect.bisect_left(sa, pattern, key=lambda i: s[i:i + len(pattern)])
    right = bisect.bisect_right(sa, pattern, key=lambda i: s[i:i + len(pattern)])
    return sorted(sa[left:right])


s = 'banana'
sa = suffix_array(s)
print(find_occurrences(s, sa, 'ana'))   # [1, 3]
print(find_occurrences(s, sa, 'na'))    # [2, 4]

Сложность — O(m log n): log n шагов бинарного поиска, каждый со сравнением строк за O(m).

Заметьте: все вхождения образца лежат подряд в суффиксном массиве, потому что все начинаются с одного префикса. Это и позволяет найти диапазон двумя бинарными поисками.

Массив LCP

Суффиксный массив редко используют в одиночку. Его почти всегда дополняют массивом LCP (longest common prefix): lcp[i] — длина наибольшего общего префикса суффиксов sa[i] и sa[i-1].

sa:   [5, 3, 1, 0, 4, 2]
суф:   a  ana  anana  banana  na  nana
lcp:   -   1     3      0      0   2

LCP считается за O(n) алгоритмом Касаи:

def build_lcp(s: str, sa: list[int]) -> list[int]:
    n = len(s)
    rank = [0] * n
    for i, pos in enumerate(sa):
        rank[pos] = i

    lcp = [0] * n
    h = 0

    for i in range(n):
        if rank[i] > 0:
            j = sa[rank[i] - 1]
            # h не может упасть больше чем на 1 при переходе к следующему i
            while i + h < n and j + h < n and s[i + h] == s[j + h]:
                h += 1
            lcp[rank[i]] = h
            if h:
                h -= 1
        else:
            h = 0

    return lcp


s = 'banana'
sa = suffix_array(s)
print(build_lcp(s, sa))   # [0, 1, 3, 0, 0, 2]

Линейность держится на неочевидном свойстве: при переходе к следующей позиции значение h уменьшается не более чем на единицу, поэтому суммарное число операций O(n).

Что решает связка «суффиксный массив + LCP»

Наибольшая повторяющаяся подстрока — это максимум в массиве LCP.

def longest_repeated(s: str) -> str:
    sa = suffix_array(s)
    lcp = build_lcp(s, sa)
    best = max(range(len(lcp)), key=lambda i: lcp[i])
    return s[sa[best]:sa[best] + lcp[best]]


print(longest_repeated('banana'))   # 'ana'

Количество различных подстрок — общее число подстрок минус сумма LCP:

n(n+1)/2 − Σ lcp[i]

Наибольшая общая подстрока двух строк — склеить их через разделитель, построить суффиксный массив и искать максимум LCP среди соседей из разных исходных строк.

Наименьший циклический сдвиг — построить массив для удвоенной строки.

Суффиксный массив или суффиксное дерево

На практике суффиксный массив почти всегда предпочтительнее: он занимает в разы меньше памяти, проще пишется, а вместе с LCP решает те же задачи. Суффиксные деревья остались в основном в учебниках и специализированных областях.

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

Отсутствие стража. Без него суффиксы, где один является префиксом другого, могут отсортироваться неверно.

Сравнение строк вместо рангов. Сводит на нет всю оптимизацию: сложность возвращается к O(n² log n).

Забытый выход при различных рангах. Без проверки rank[sa[-1]] == n - 1 алгоритм отработает лишние итерации, хотя ответ уже готов.

Смешение индексов sa и rank. sa[i] — позиция i-го по порядку суффикса, rank[i] — порядковый номер суффикса, начинающегося в позиции i. Это обратные друг другу массивы, и путать их легко.

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

• Суффиксный массив — отсортированные позиции всех суффиксов, память O(n).
• Строится удвоением: на шаге k сортируем по парам рангов предыдущего шага.
• Поиск подстроки — бинарный поиск за O(m log n), вхождения лежат подряд.
• Массив LCP считается за O(n) и вместе с массивом решает большинство строковых задач.
• На практике предпочтительнее суффиксного дерева: меньше памяти и проще код.

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

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

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

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

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