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

Коротко

Суффиксный автомат — минимальный конечный автомат, распознающий все суффиксы строки. Его главное свойство: пути из начального состояния соответствуют всем подстрокам, и при этом состояний линейно мало.

Что он умеет

Одна структура закрывает целый класс задач:

• проверить, является ли строка подстрокой, за O(её длины);
• посчитать количество различных подстрок;
• найти количество вхождений каждой подстроки;
• найти наибольшую общую подстроку двух строк;
• найти k-ю в лексикографическом порядке подстроку;
• найти наименьший циклический сдвиг.

Всё это при линейной памяти — там, где наивное хранение всех подстрок потребовало бы O(n²).

Ключевые понятия

Состояние автомата соответствует множеству подстрок, у которых одинаковое множество позиций окончаний. Такие подстроки объединяются в один класс эквивалентности — отсюда и берётся экономия.

len[v] — длина самой длинной строки в классе v.

link[v] — суффиксная ссылка: ведёт в состояние, соответствующее наибольшему суффиксу, который попадает в другой класс.

Суффиксные ссылки образуют дерево — оно называется суффиксным деревом ссылок и само по себе полезно для решения задач.

Построение

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

class SuffixAutomaton:
    def __init__(self):
        # состояние: переходы, суффиксная ссылка, длина
        self.next = [{}]
        self.link = [-1]
        self.len = [0]
        self.last = 0

    def extend(self, ch: str) -> None:
        cur = len(self.next)
        self.next.append({})
        self.len.append(self.len[self.last] + 1)
        self.link.append(-1)

        p = self.last
        # добавляем переходы, пока их нет
        while p != -1 and ch not in self.next[p]:
            self.next[p][ch] = cur
            p = self.link[p]

        if p == -1:
            self.link[cur] = 0            # дошли до корня
        else:
            q = self.next[p][ch]

            if self.len[p] + 1 == self.len[q]:
                self.link[cur] = q        # переход «непрерывный»
            else:
                # клонируем состояние q
                clone = len(self.next)
                self.next.append(dict(self.next[q]))
                self.len.append(self.len[p] + 1)
                self.link.append(self.link[q])

                while p != -1 and self.next[p].get(ch) == q:
                    self.next[p][ch] = clone
                    p = self.link[p]

                self.link[q] = clone
                self.link[cur] = clone

        self.last = cur

    def build(self, s: str) -> 'SuffixAutomaton':
        for ch in s:
            self.extend(ch)
        return self

    def contains(self, pattern: str) -> bool:
        v = 0
        for ch in pattern:
            if ch not in self.next[v]:
                return False
            v = self.next[v][ch]
        return True


sa = SuffixAutomaton().build('abcbc')

print(sa.contains('bcb'))    # True
print(sa.contains('abc'))    # True
print(sa.contains('acb'))    # False
print('состояний:', len(sa.next))

Клонирование — самая неочевидная часть. Оно нужно, когда существующее состояние q содержит строки разной «природы»: часть из них является суффиксами нового префикса, часть нет. Клон разделяет эти случаи.

Почему состояний линейно мало

Доказано: у суффиксного автомата строки длины n не больше 2n − 1 состояний и 3n − 4 переходов.

Это удивительный результат — различных подстрок может быть до n(n+1)/2, то есть квадратично много, но они группируются в линейное число классов эквивалентности.

Задача: количество различных подстрок

Классическое применение. Каждое состояние v кроме корня представляет ровно len[v] − len[link[v]] различных подстрок.

def count_distinct_substrings(s: str) -> int:
    sa = SuffixAutomaton().build(s)
    return sum(
        sa.len[v] - sa.len[sa.link[v]]
        for v in range(1, len(sa.next))
    )


print(count_distinct_substrings('abc'))    # 6: a, b, c, ab, bc, abc
print(count_distinct_substrings('aaa'))    # 3: a, aa, aaa
print(count_distinct_substrings('abcbc'))  # 12

Проверьте на aaa: наивно подстрок 6, но различных только 3. Автомат считает правильно и за линейное время.

Задача: наибольшая общая подстрока

Строим автомат по первой строке и «прогоняем» через него вторую, отслеживая текущую длину совпадения.

def longest_common_substring(a: str, b: str) -> str:
    sa = SuffixAutomaton().build(a)

    v, length = 0, 0
    best_len, best_pos = 0, 0

    for i, ch in enumerate(b):
        # если перехода нет — откатываемся по суффиксным ссылкам
        while v and ch not in sa.next[v]:
            v = sa.link[v]
            length = sa.len[v]

        if ch in sa.next[v]:
            v = sa.next[v][ch]
            length += 1
        else:
            v, length = 0, 0

        if length > best_len:
            best_len, best_pos = length, i

    return b[best_pos - best_len + 1:best_pos + 1]


print(longest_common_substring('abcbc', 'xbcby'))   # 'bcb'

Сложность — O(|a| + |b|). Через динамическое программирование та же задача решалась бы за O(|a|·|b|).

Сравнение с соседними структурами

Суффиксный автомат — хороший баланс: строится онлайн за линейное время, код компактнее суффиксного дерева, а задачи про подстроки решает элегантнее суффиксного массива.

Слабое место — память при большом алфавите: словарь переходов в каждом состоянии.

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

Пропуск клонирования. Автомат построится, но будет распознавать лишние строки. Ошибка проявляется только на определённых входах.

Копирование переходов клона по ссылке. self.next[q] нужно копировать (dict(...)), иначе изменения затронут оригинал.

Неверный len у клона. Должно быть len[p] + 1, а не len[q]. Это ломает подсчёт различных подстрок.

Забытый откат по суффиксным ссылкам при поиске общей подстроки. Без него алгоритм теряет совпадения.

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

• Суффиксный автомат распознаёт все подстроки строки, имея не более 2n−1 состояний.
• Строится онлайн, символ за символом, за линейное время.
• Состояние объединяет подстроки с одинаковым множеством позиций окончаний.
• Количество различных подстрок — сумма len[v] − len[link[v]] по всем состояниям.
• Наибольшая общая подстрока двух строк находится за O(n + m).

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

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

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

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

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