Префиксные деревья, суффиксные массивы и строковые структуры

Все структуры, которые мы разбирали до сих пор, относились к ключу как к атомарной точке. Хеш-таблица сминает ключ в одно число и теряет о нём всё остальное. Дерево поиска умеет сравнивать ключи, но каждое сравнение — чёрный ящик, возвращающий «меньше/больше».

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

1. Если ключ — путь, то его можно не хранить целиком в одном месте: общий префикс тысячи слов достаточно записать один раз. Это идея бора (trie).
2. Если строка длинная, то интересны не только её ключи, но и все её подстроки. Их Θ(n²) штук, но все они — префиксы всего лишь n суффиксов. Это идея суффиксных структур.

Разберём оба семейства: от наивного бора до сжатых и succinct-вариантов, от автомата Ахо-Корасик до суффиксного массива с LCP. Всюду — работающий код, честная асимптотика и то, где это реально применяется. Предполагается знакомство с асимптотикой и моделью памяти и массивами и строками.

Карта территории

Ключевое разделение: префиксные структуры индексируют множество ключей и отвечают на вопросы «есть ли такой ключ», «какие ключи начинаются с P». Суффиксные индексируют одну (возможно, гигантскую) строку и отвечают на вопрос «где внутри неё встречается P». Путаница между этими двумя задачами — источник половины неудачных решений на собеседованиях и в проде.

Бор: ключ как путь

Определение простое. Бор (trie, от retrieval) — дерево, в котором каждое ребро помечено символом, а каждый узел соответствует префиксу, полученному конкатенацией меток на пути от корня. Узлы, соответствующие полноценным ключам, помечены флагом is_word.

Три следствия, которые надо прочувствовать:

• Сам ключ нигде не хранится. Он «размазан» по пути. Узел не знает своей строки.
• Стоимость операции зависит только от длины ключа m, а не от размера словаря n. Поиск — O(m), вставка — O(m). При n = 10⁹ и m = 8 бор делает 8 шагов, а сбалансированное дерево — 30 сравнений строк.
• Порядок ключей получается бесплатно. Обход в глубину с сортировкой детей даёт лексикографически отсортированный список — то, чего не умеет хеш-таблица.

Флаг is_word — не мелочь, а суть. Без него нельзя отличить ключ "do" от префикса "do" слова "dog". Это ошибка №1 в реализациях бора.

class TrieNode:
    __slots__ = ("children", "is_word", "count")  # __slots__ экономит ~50% памяти узла

    def __init__(self):
        self.children = {}   # символ -> TrieNode
        self.is_word = False # здесь заканчивается настоящий ключ
        self.count = 0       # сколько ключей проходит через этот узел (для автодополнения)


class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        """O(m) по времени, O(m) новых узлов в худшем случае."""
        node = self.root
        for ch in word:
            node.count += 1
            nxt = node.children.get(ch)
            if nxt is None:
                nxt = TrieNode()
                node.children[ch] = nxt
            node = nxt
        node.count += 1
        node.is_word = True

    def _walk(self, prefix):
        """Спуск по префиксу. None, если такого пути нет."""
        node = self.root
        for ch in prefix:
            node = node.children.get(ch)
            if node is None:
                return None
        return node

    def search(self, word):
        node = self._walk(word)
        return node is not None and node.is_word   # ВАЖНО: не просто "путь существует"

    def starts_with(self, prefix):
        return self._walk(prefix) is not None

    def count_with_prefix(self, prefix):
        """O(|prefix|) — счётчик посчитан заранее, поддерево обходить не нужно."""
        node = self._walk(prefix)
        return node.count if node else 0

    def complete(self, prefix, limit=10):
        """Автодополнение: DFS по поддеревью префикса, лексикографический порядок."""
        node = self._walk(prefix)
        if node is None:
            return []
        out, stack = [], [(node, prefix)]
        while stack and len(out) < limit:
            cur, path = stack.pop()
            if cur.is_word:
                out.append(path)
            for ch in sorted(cur.children, reverse=True):  # reverse — чтобы pop дал 'a' первым
                stack.append((cur.children[ch], path + ch))
        return out

>>> t = Trie()
>>> for w in ["car", "card", "care", "cat", "dog", "do"]: t.insert(w)
>>> t.search("car"), t.search("ca"), t.search("do")
(True, False, True)
>>> t.count_with_prefix("ca"), t.complete("ca")
(4, ['car', 'card', 'care', 'cat'])

Обратите внимание на count: он превращает «сколько слов начинается с ca» из обхода поддерева O(размер поддерева) в O(|префикса|). Тот же приём — хранить агрегат в узле — работает для максимального веса в поддереве, и именно так строят автодополнение с ранжированием: спускаемся по префиксу, затем ведём приоритетную очередь по узлам, упорядоченным по «максимальному весу в поддереве» (кучи), и вытаскиваем top-k, не обходя поддерево целиком.

Сложность и — главное — память

Время у бора прекрасное и гарантированное в худшем случае — в отличие от хеш-таблицы, где O(1) только в среднем и рушится при коллизионной атаке. А вот память — ахиллесова пята.

Посчитаем честно. Словарь на 1 000 000 слов, средняя длина 8 → примерно 5–6 миллионов узлов (префиксы схлопываются, но не сильно). Узел на Python со __slots__ и пустым dict — порядка 150–250 байт. Итого больше гигабайта на словарь, который в виде плоского текста занимает 10 МБ. Наивный бор проигрывает по памяти в сто раз.

Если пойти другим путём и сделать children массивом на 256 указателей, станет ещё хуже: 2 КБ на узел, из которых занято 1–2 ячейки. Для Unicode массив вообще невозможен.

Это ошибка №2: бор для больших словарей нельзя реализовывать в лоб. Дальше — три способа это чинить.

Сжатый бор: убираем цепочки без ветвления

Первое наблюдение: в боре полно узлов ровно с одним ребёнком. Они не несут информации — только тратят указатель и промах кеша. Схлопнем каждую такую цепочку в один узел с меткой-строкой.

Получится сжатый бор (compressed trie), он же radix tree, он же PATRICIA (Practical Algorithm To Retrieve Information Coded In Alphanumeric, Morrison, 1968).

Ключевое свойство: у каждого внутреннего узла сжатого бора минимум два ребёнка, поэтому для n ключей число узлов не превышает 2n − 1 — оно зависит от количества ключей, а не от суммарной длины. Это качественно другая оценка памяти.

Второй выигрыш — по кешу. Метка ребра сравнивается целыми машинными словами (memcmp), а не по символу с разыменованием указателя на каждом шаге. Учитывая, что промах в оперативную память стоит около 100 нс, а сравнение 8 байт в регистре — доли наносекунды, разница на практике огромная.

class RadixNode:
    __slots__ = ("edges", "is_word")

    def __init__(self):
        self.edges = {}      # первый символ метки -> (метка, RadixNode)
        self.is_word = False


def radix_insert(node, key):
    """Вставка со всеми тремя случаями расщепления. O(|key|)."""
    while True:
        if not key:
            node.is_word = True
            return
        head = key[0]
        if head not in node.edges:                 # случай 1: новой ветки нет
            leaf = RadixNode()
            leaf.is_word = True
            node.edges[head] = (key, leaf)
            return

        label, child = node.edges[head]
        # длина общего префикса метки и остатка ключа
        i = 0
        while i < len(label) and i < len(key) and label[i] == key[i]:
            i += 1

        if i == len(label):                        # случай 2: метка целиком съедена
            node, key = child, key[i:]
            continue

        # случай 3: метка расщепляется посередине
        middle = RadixNode()
        middle.edges[label[i]] = (label[i:], child)
        node.edges[head] = (label[:i], middle)
        if i == len(key):
            middle.is_word = True                  # ключ закончился ровно в точке расщепления
        else:
            leaf = RadixNode()
            leaf.is_word = True
            middle.edges[key[i]] = (key[i:], leaf)
        return

Три случая расщепления — то место, где ломаются почти все самописные реализации. Отдельно проверяйте случай, когда новый ключ является префиксом уже вставленного ("card" есть, вставляем "car"): узел расщепления должен получить is_word = True, а не новый лист.

Где это живёт в проде:

• Linux, таблица маршрутизации. net/ipv4/fib_trie.c — LC-trie (level-compressed trie, Nilsson & Karlsson), сжатый бор над битами IP-адреса. Longest-prefix match — это буквально «самый глубокий узел на пути», за что боры и любят в роутинге. kernel.org: fib_trie
• Redis. Структура rax — сжатый radix tree, на нём построены ID потоков (Streams), списки клиентов и слежение за ключами. github.com/antirez/rax
• Ethereum. Merkle Patricia Trie — состояние всего блокчейна, где сжатие критично, а хеши узлов дают криптографические доказательства включения.
• Go, net/netip и многие роутеры HTTP (httprouter, Gin, Echo) — маршруты вида /api/v1/users/:id разбираются radix-деревом за один проход по URL. См. обзор Go.

Куда идти дальше по памяти: TST, double-array и succinct

Если и сжатого бора мало, есть три классических приёма:

• Тернарный бор (ternary search trie, Bentley & Sedgewick, 1997): у узла три указателя — «меньше», «равно», «больше». Память как у BST, поиск O(m + log σ), отлично работает для больших алфавитов. Подробный разбор — у Sedgewick, Algorithms 5.2.
• Double-array trie (Aoe, 1989): весь бор кодируется двумя целочисленными массивами base и check — ноль указателей, переход за одно обращение к массиву. Основа японских морфологических анализаторов MeCab и библиотеки darts.
• Succinct-структуры: LOUDS-trie кодирует форму дерева в 2n + o(n) бит и всё равно отвечает на запросы за O(1) на шаг. Обзор — Navarro, Compact Data Structures.
• FST (finite state transducer) — бор, у которого схлопнуты не только общие префиксы, но и общие суффиксы (то есть DAWG с выходными значениями). Это то, чем Lucene и, соответственно, Elasticsearch хранят словарь термов: гигантский словарь ужимается в единицы процентов исходного размера и при этом остаётся отображением «терм → offset». Классический разбор от автора Lucene

Ахо-Корасик: тысяча шаблонов за один проход

Задача: есть набор шаблонов P₁…P_k (стоп-слова, сигнатуры вирусов, названия брендов, токены словаря) и длинный текст. Нужны все вхождения всех шаблонов.

Наивно — запустить поиск подстроки k раз: O(k·(n + m)). При k = 100 000 сигнатур и потоке трафика это неприемлемо. Ахо-Корасик (1975) делает это за один проход: O(n + число вхождений), независимо от k.

Идея: построить бор из шаблонов, а затем добавить суффиксные ссылки (fail links). fail[v] ведёт в узел, соответствующий самому длинному собственному суффиксу строки узла v, который сам является узлом бора. Это ровно обобщение префикс-функции КМП на множество шаблонов. Получается детерминированный конечный автомат: если из текущего состояния нет перехода по символу, идём по fail-ссылке и пробуем снова.

Именно из-за fail-ссылок находится вложенное вхождение: в тексте ushers шаблон she заканчивается на позиции 3, и одновременно там же заканчивается he. Если не «протянуть» списки выходов по fail-ссылкам, вложенные шаблоны будут молча теряться — ошибка №3, и самая коварная, потому что тесты на непересекающихся шаблонах её не ловят.

from collections import deque


class AhoCorasick:
    """Многошаблонный поиск. Построение O(Σ|Pi|), поиск O(n + occ)."""

    def __init__(self, patterns):
        self.next = [{}]   # переходы бора: узел -> {символ: узел}
        self.fail = [0]    # суффиксные ссылки
        self.out = [[]]    # индексы шаблонов, заканчивающихся здесь (уже с протяжкой)

        for idx, p in enumerate(patterns):          # 1) строим бор
            v = 0
            for ch in p:
                if ch not in self.next[v]:
                    self.next.append({})
                    self.fail.append(0)
                    self.out.append([])
                    self.next[v][ch] = len(self.next) - 1
                v = self.next[v][ch]
            self.out[v].append(idx)

        q = deque()                                  # 2) BFS проставляет fail-ссылки
        for ch, u in self.next[0].items():
            self.fail[u] = 0                         # дети корня всегда падают в корень
            q.append(u)
        while q:
            v = q.popleft()
            for ch, u in self.next[v].items():
                f = self.fail[v]
                while f and ch not in self.next[f]:  # спускаемся по суффиксным ссылкам
                    f = self.fail[f]
                self.fail[u] = self.next[f].get(ch, 0)
                # протяжка выходов: BFS гарантирует, что out[fail[u]] уже полон
                self.out[u] = self.out[u] + self.out[self.fail[u]]
                q.append(u)

    def find(self, text):
        """Отдаёт (позиция конца вхождения, индекс шаблона)."""
        v = 0
        for i, ch in enumerate(text):
            while v and ch not in self.next[v]:
                v = self.fail[v]
            v = self.next[v].get(ch, 0)
            for idx in self.out[v]:
                yield i, idx

>>> pats = ["he", "she", "his", "hers"]
>>> list((i, pats[k]) for i, k in AhoCorasick(pats).find("ushers"))
[(3, 'she'), (3, 'he'), (5, 'hers')]

Почему поиск линеен, хотя внутри есть while? Классический аргумент амортизации (см. асимптотику и амортизацию): глубина текущего узла растёт максимум на 1 за символ, а каждый шаг по fail-ссылке уменьшает её минимум на 1. Значит, суммарное число таких шагов за весь проход не превосходит n.

Практические замечания:

• Замена dict на массив переходов превращает автомат в полную таблицу σ × (число узлов): поиск становится одним обращением к массиву без цикла, ценой памяти. Это стандартный размен для сетевых DPI-движков.
• Hyperscan от Intel — продакшн-реализация именно этого класса идей (плюс SIMD и декомпозиция регулярных выражений); используется в Suricata и Snort. github.com/intel/hyperscan
• В Python на практике часто быстрее скомпилировать один регэксп re.compile("|".join(...)) для сотни шаблонов, чем писать автомат на чистом Python: движок написан на C. Ахо-Корасик выигрывает от тысяч шаблонов и от реализации на компилируемом языке (pyahocorasick, aho-corasick в Rust).

Суффиксные структуры: индексируем одну строку

Смена задачи. Раньше было множество ключей; теперь — одна строка s длиной n, и вопросы про подстроки: где встречается P, сколько раз, какая самая длинная повторяющаяся, какая самая длинная общая с другой строкой.

Ключевое наблюдение: подстрок Θ(n²), но каждая подстрока — префикс какого-то суффикса. Суффиксов всего n, и каждый задаётся одним числом. Значит, проиндексировав n суффиксов, мы проиндексировали все n(n+1)/2 подстрок.

Исторически первым был суффиксный бор — бор из всех суффиксов. Он имеет Θ(n²) узлов (строка aaa…a), поэтому его сжимают, получая суффиксное дерево: линейное число узлов, построение за O(n) (Weiner 1973, McCreight 1976, Ukkonen 1995 — последний онлайновый и человекопонятный). Суффиксное дерево решает десятки задач и стало легендой.

И тем не менее в проде его чаще не используют. Причина — константа памяти: узел хранит до σ указателей, границы метки и суффиксную ссылку, что даёт 20 n байт в аккуратных реализациях и до 40 n в наивных. Для генома человека (3·10⁹ символов) это 60–120 ГБ.

Суффиксный массив: то же самое, но в 4n байт

Суффиксный массив SA — это перестановка индексов 0…n−1, отсортированная по лексикографическому порядку соответствующих суффиксов. Один массив int32. И всё.

Манбер и Майерс (1990) показали, что почти всё, что умеет суффиксное дерево, умеет и SA, если добавить LCP-массив: LCP[i] — длина наибольшего общего префикса суффиксов рангов i−1 и i.

Три вещи, которые надо увидеть на этой картинке:

1. Суффиксы с общим префиксом лежат подряд. Поэтому все вхождения образца P — это непрерывный отрезок SA, находимый бинарным поиском.
2. LCP — это «высоты» между соседями. Максимум LCP = самая длинная повторяющаяся подстрока.
3. Число различных подстрок = n(n+1)/2 − Σ LCP: из всех префиксов всех суффиксов вычитаем те, что уже были учтены соседом слева.

Построение: удвоение префиксов

Наивная сортировка sorted(range(n), key=lambda i: s[i:]) — это O(n² log n), потому что каждое сравнение строк стоит O(n), а срезы ещё и копируют. На строке в 1 МБ это часы. Ошибка №4 и очень частая.

Правильный базовый метод — удвоение (prefix doubling): сортируем суффиксы по первым 2^k символам, используя ранги предыдущего шага как ключи. Каждое сравнение становится сравнением пары чисел за O(1).

def suffix_array(s):
    """Удвоение префиксов. O(n log^2 n) со встроенным sort, O(n) памяти."""
    n = len(s)
    if n == 0:
        return []
    rank = [ord(c) for c in s]
    sa = sorted(range(n), key=lambda i: rank[i])
    k, tmp = 1, [0] * n
    while True:
        def key(i):
            # -1 для «строка кончилась»: пустой суффикс меньше любого символа
            return (rank[i], rank[i + k] if i + k < n else -1)

        sa.sort(key=key)                      # стабильная сортировка по паре рангов
        tmp[sa[0]] = 0
        for j in range(1, n):
            tmp[sa[j]] = tmp[sa[j - 1]] + (key(sa[j - 1]) < key(sa[j]))
        rank = tmp[:]
        if rank[sa[-1]] == n - 1:             # все ранги различны — сортировка завершена
            return sa
        k *= 2

Здесь O(n log² n): log n итераций удвоения × O(n log n) на сортировку. Заменив сортировку на поразрядную по двум ключам, получаем O(n log n) — это и есть алгоритм Манбера-Майерса. Существуют и линейные: DC3/skew (Kärkkäinen & Sanders, 2003) и SA-IS (Nong, Zhang, Chan, 2009) — последний и прост, и быстр на практике; именно его варианты стоят в libdivsufsort и в биоинформатических индексаторах.

LCP за линейное время: алгоритм Касаи

Наивно LCP считается за O(n²). Касаи и соавторы (2001) заметили: если идти по суффиксам в порядке позиции в строке, а не в порядке ранга, то значение LCP падает максимум на 1 за шаг. Значит, счётчик h можно не сбрасывать.

def kasai(s, sa):
    """LCP-массив за O(n). lcp[i] = LCP(suffix(sa[i-1]), suffix(sa[i])), lcp[0] = 0."""
    n = len(s)
    rank = [0] * n
    for i, p in enumerate(sa):
        rank[p] = i
    lcp, h = [0] * n, 0
    for i in range(n):                 # i — позиция в строке, НЕ ранг
        if rank[i] == 0:
            h = 0                      # у первого в порядке соседа слева нет
            continue
        j = sa[rank[i] - 1]            # сосед по рангу
        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                     # ключевой трюк: переходя к i+1, теряем максимум 1
    return lcp

Амортизация та же, что у Ахо-Корасик: h растёт суммарно не более чем на n и убывает не более чем на 1 за итерацию, значит внутренний цикл суммарно делает O(n) шагов.

lcp[0] не определён — это позиция, у которой нет соседа слева. Соглашение «класть туда 0» безобидно, но если вы ищете максимум LCP по всему массиву, помните, что нулевой элемент фиктивный. Ошибка №5, классический off-by-one.

Что это даёт

def sa_range(s, sa, pat):
    """Полуинтервал рангов [l, r) со всеми вхождениями pat. O(|pat| * log n)."""
    m = len(pat)
    lo, hi = 0, len(sa)
    while lo < hi:                                   # нижняя граница
        mid = (lo + hi) // 2
        if s[sa[mid]:sa[mid] + m] < pat:
            lo = mid + 1
        else:
            hi = mid
    left, hi = lo, len(sa)
    while lo < hi:                                   # верхняя граница
        mid = (lo + hi) // 2
        if s[sa[mid]:sa[mid] + m] <= pat:
            lo = mid + 1
        else:
            hi = mid
    return left, lo

>>> s = "banana"
>>> sa = suffix_array(s); lcp = kasai(s, sa)
>>> sa, lcp
([5, 3, 1, 0, 4, 2], [0, 1, 3, 0, 0, 2])
>>> sa_range(s, sa, "ana")                  # два вхождения: позиции 3 и 1
(1, 3)
>>> max(lcp)                                # самая длинная повторяющаяся подстрока
3
>>> len(s) * (len(s) + 1) // 2 - sum(lcp)   # число различных подстрок
15

Типовой набор задач, решаемых SA + LCP:

Последняя строка важна: LCP(i, j) = min на отрезке LCP-массива, то есть задача range minimum query. С разреженной таблицей или деревом отрезков SA + LCP становится полноценной заменой суффиксного дерева — это и называется enhanced suffix array (Abouelhoda, Kurtz, Ohlebusch, 2004).

Сжатые индексы: BWT и FM-index

Даже 4n байт много, если n = 3·10⁹. Следующий шаг — сжатые самоиндексирующиеся структуры: преобразование Бэрроуза-Уилера (BWT) плюс FM-index (Ferragina & Manzini, 2000). BWT — перестановка символов строки, тесно связанная с суффиксным массивом (BWT[i] = s[SA[i] − 1]); она группирует одинаковые символы вместе, отчего отлично сжимается. FM-index добавляет к сжатой BWT ранговые структуры и умеет искать образец не разжимая текст, за O(|P|) обращений.

Практический итог: геном человека индексируется в 1–2 ГБ вместо 60. На этом стоят bwa и bowtie — стандартные инструменты выравнивания прочтений ДНК, а также ripgrep-подобные подходы к статическим большим корпусам.

Как выбирать

Отдельно подчеркну самую частую стратегическую ошибку: бор берут там, где хватило бы хеш-таблицы. Если единственный запрос — «есть ли такой ключ», хеш-таблица проще, быстрее и компактнее. Бор оправдан ровно тогда, когда нужен один из его уникальных запросов: префиксный поиск, longest prefix match, лексикографический порядок или разделение памяти между похожими ключами. Симметрично, суффиксный массив бессмысленно строить, если по тексту делается один поиск: построение стоит дороже, чем сам поиск наивным алгоритмом.

Типичные ошибки

1. Нет флага is_word. Нельзя отличить ключ от префикса. Тесты на словаре без вложенных слов это не поймают — добавьте пару do / dog.
2. Массив на 256 (или 65536) детей в каждом узле. Мгновенный взрыв памяти. Для разреженных узлов — словарь или отсортированный маленький массив, для плотных — битовая маска + компактный массив (подход HAMT/ART).
3. Ахо-Корасик без протяжки out по fail-ссылкам. Вложенные шаблоны теряются молча.
4. Построение SA сортировкой суффиксов «в лоб». O(n² log n) и копирование срезов. Используйте удвоение, а лучше готовую библиотеку с SA-IS.
5. Забыть, что lcp[0] фиктивный — или, зеркально, сдвинуть весь массив на 1 и ловить off-by-one в каждом запросе.
6. Считать символы там, где нужны байты (или наоборот). В UTF-8 «символ» — это 1–4 байта, а «то, что видит пользователь» — это графемный кластер, который может состоять из нескольких кодовых точек (эмодзи с модификаторами, é как e + U+0301). Бор, построенный по байтам, будет корректен для точного поиска и некорректен для регистронезависимого. Перед индексацией — нормализация NFC и case folding, а не lower(). См. Unicode TR15.
7. Использовать бор как замену хеш-таблице «потому что O(m)». См. выше: m — это длина ключа, и она у вас, скорее всего, не меньше стоимости одного хеширования.
8. Хранить в узле полную строку ключа «для удобства». Это убивает единственное преимущество бора по памяти — разделение префиксов.

Мини-итог

• Строка — это путь, а не точка. Бор материализует эту идею: узел = префикс, операция стоит O(длины ключа) в худшем случае и не зависит от размера словаря.
• Уникальные суперспособности бора — префиксные запросы, longest prefix match и лексикографический порядок. Только ради них его и стоит брать: для «есть/нет» хеш-таблица лучше.
• Наивный бор проигрывает по памяти в десятки раз. Лечится сжатием цепочек (radix / PATRICIA, ≤ 2n−1 узлов), тернарными борами, double-array, succinct-кодированием и FST со схлопыванием суффиксов.
• Ахо-Корасик = бор + суффиксные ссылки = автомат, находящий все вхождения всех шаблонов за O(n + occ) независимо от их количества. Не забывайте протягивать списки выходов.
• Все подстроки строки — префиксы её n суффиксов. Отсюда суффиксные структуры. Суффиксное дерево красиво, но стоит 20n байт; суффиксный массив + LCP даёт почти ту же функциональность в 8n байт, а FM-index — в пределах размера сжатого текста.
• Строится SA удвоением префиксов за O(n log n) (в проде — SA-IS за O(n)), LCP — алгоритмом Касаи за O(n). Оба линейных результата опираются на один и тот же амортизационный аргумент.

Источники

• Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms, 4-е изд., гл. 32 (сопоставление строк) — mitpress.mit.edu
• Sedgewick, Wayne. Algorithms, 4th ed., гл. 5.2 «Tries» — algs4.cs.princeton.edu/52trie
• Gusfield. Algorithms on Strings, Trees, and Sequences — каноническая книга по суффиксным деревьям — doi.org/10.1017/CBO9780511574931
• Morrison. PATRICIA — Practical Algorithm To Retrieve Information Coded in Alphanumeric (1968) — dl.acm.org/doi/10.1145/321479.321481
• Aho, Corasick. Efficient String Matching: An Aid to Bibliographic Search (1975) — dl.acm.org/doi/10.1145/360825.360855
• Bentley, Sedgewick. Fast Algorithms for Sorting and Searching Strings (1997) — cs.princeton.edu/~rs/strings
• Manber, Myers. Suffix Arrays: A New Method for On-Line String Searches (1990) — doi.org/10.1137/0222058
• Ukkonen. On-line Construction of Suffix Trees (1995) — cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf
• Kasai et al. Linear-Time Longest-Common-Prefix Computation in Suffix Arrays (2001) — doi.org/10.1007/3-540-48194-X_17
• Nong, Zhang, Chan. Linear Suffix Array Construction by Almost Pure Induced-Sorting (SA-IS, 2009) — doi.org/10.1109/DCC.2009.42
• Ferragina, Manzini. Opportunistic Data Structures with Applications (FM-index, 2000) — doi.org/10.1109/SFCS.2000.892127
• Abouelhoda, Kurtz, Ohlebusch. Replacing Suffix Trees with Enhanced Suffix Arrays (2004) — doi.org/10.1016/S1570-8667(03)00065-0
• Navarro. Compact Data Structures: A Practical Approach — users.dcc.uchile.cl/~gnavarro/CDSbook
• Leis et al. The Adaptive Radix Tree (ART) (2013) — бор с адаптивным размером узла для in-memory СУБД — db.in.tum.de/~leis/papers/ART.pdf
• Linux kernel: fib_trie — docs.kernel.org/networking/fib_trie.html
• Lucene FST — blog.mikemccandless.com
• Redis rax — github.com/antirez/rax

Что дальше

Ахо-Корасик, который мы построили, — это конечный автомат, то есть граф состояний с переходами. Суффиксные ссылки образуют в нём отдельное дерево. Radix-дерево маршрутизации в ядре — тоже граф. Мы всё время незаметно работали с графами, просто с очень специальными: деревьями и автоматами.

Пора разобраться с графами в общем виде: как их вообще представлять в памяти (матрица смежности, списки смежности, CSR), как этот выбор меняет стоимость каждой операции на порядки, и почему для разреженных графов ответ почти всегда один и тот же.

Следующая статья: Графы: представления, свойства и выбор структуры.