suffix-automaton.md

Суффиксный автомат

Если вы не знаете, что такое префиксное дерево или автомат, рекомендуется сначала почитать про Ахо-Корасик.

Рассмотрим задачу:

Дан текст $T$ и $n$ строк $s_i$, для каждой из которых нужно узнать, встречается ли она в тексте.

Есть два основных подхода к решению этой задачи. Первый: алгоритм Ахо-Корасик, который строит по набору строк автомат, распознающий эти строки в потоке текста. Второй: использование суффиксных структур, под которыми обычно подразумневают суффиксный массив, суффиксный автомат или суффикское дерево.

Данная статья посвящена последним двум из них.

Наивное решение

Возьмем все суффиксы $T$ и объединим их в бор, в котором каждой подстроке $T$ будет соответствовать ровно одна вершина. С его помощью можно за $O(|T|^2)$ времени на построение и $O(|s_i|)$ времени на запрос узнавать, входит ли $s_i$ в $T$.

Идея дальнейшей оптимизации заключается в убирании «лишних» состояний в этом боре.

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

Сжатое суффиксное дерево. Любой путь от корня в этом боре будет подстрокой $T$, а значит, если из вершины $v$ нет исходящий рёбер, то можно заменить путь на ребро, храня рядом с ним всю строку. Непосредственно хранить строку при этом не обязательно — она есть где-то как подстрока $T$, а значит можно просто хранить пару чисел $[l, r]$, указывающую на её местоположение.

Выясняется, что такая структура данных занимает $O(|T|)$ памяти. Чтобы это понять, нужно оценить количество «развилок» — мест, где путь разъеденяется на два.

Пусть мы бор строли путем добавления суффиксов. Тогда, каждая новая строка совпадала каким-то префиксом с уже имеющейся, а потом отпочковалась и породила новый путь. Получается, что вершин тут не больше, чем строк.

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

Существуют алгоритмы, которые строят сжатое суффиксное дерево эффективно — например, алгортим Укконена. Мы их рассматривать в этой статье не будем и сразу перейдём ко второму методу.

Суффиксным автоматом строки $s$ называется минимальный (с наименьшим количеством вершин) детерминированный (нет двух различных путей, соответствующих одинаковой строке) автомат, принимающий все различные подстроки $s$ и только их.

Выясняется, что он тоже маленький, и если хранить переходы в std::map, то автомат можно построить за $O(n log k)$ времени и $O(n)$ памяти, где $k$ — размер алфавита (обычно $k$ считают константой, и тогда построение происходит вообще за $O(n)$).

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

Любое состояние $V$ автомата будет принимать некоторый набор строк $T$, причём если отсортировать эти строки по возрастанию длины, то для любой строки $s_i \in T (i < |T|)$ следующая по порядку строка - это $s_{i+1} = cs_i$ для некоторого символа $c$. Исходя из определения суффиксного автомата, для любого префикса исходной строки $S$ существуют несколько состояний, принимающих его суффиксы: состояние $V_1$, принимающее суффиксы длин от 1 до некоторого $k_1$, состояние $V_2$, принимающее суффиксы длин от $k_1+1$ до $k_2$, и т.д. до состояния, принимающего самые длинные суффиксы данного префикса, включая сам префикс. Из каждого состояния $X$, кроме корневого, существует суффиксная ссылка: пусть $X$ принимает некоторую строку $p$, тогда суффиксная ссылка из $X$ ведёт в отличное от $X$ состояние, принимающее суффикс $p$ максимальной длины. Также из каждого состояния $X$, кроме корневого, ведёт ещё одна ссылка, мы назовём её префиксной: пусть самая длинная принимаемая $X$ строка - это $p$, тогда префиксная ссылка из $X$ указывает на состояние, принимающее префикс $p$ на единицу меньшей длины.

Теперь можем перейти к алгоритму построения суффиксного автомата. Наш алгоритм будет "индуктивным": он будет перестраивать автомат, коррекно построенный для строки $s$, получая из него автомат для строки $sc$.

Предположим, что мы построили суффиксный автомат для строки $s$, удовлетворяющий всем требованиям, и теперь добавляем символ $c$. Пусть $X$ - состояние, которое принимало строку $s$ до добавления $c$. Сперва мы обязаны создать новое состояние $U$, так как появилась строка $sc$, которая ранее не входила в $s$. Затем, мы должны добавить переход из $X$ в $U$ по символу $c$ (потому что должно быть состояние, принимающее $sc$). Таким образом, наше новое состояние $U$ теперь принимает некоторый набор суффиксов $sc$. Перейдём по суффиксной ссылке из $X$. Тогда есть два случая:

1. Перехода по $c$ из текущего состояния нет. Тогда мы можем и должны добавить переход по символу $c$, ведущий в $U$: теперь $U$ принимает ещё больший набор суффиксов. Снова перейдём по суффиксной ссылке из текущего состояния и продолжим пытаться строить переходы.
2. Переход по $c$ из текущего состояния есть. Таким образом, для оставшихся суффиксов $sc$ уже существовуют свои состояния, на этом моменте следует остановиться и перейти к следующей части алгоритма.

Опять есть два случая: первый - ни из одного состояния, в котором мы побывали, перехода по $c$ не нашлось, и в итоге мы перешли по суффиксной ссылке из корня "в никуда". Тогда все суффиксы $sc$ принимаются одним состоянием $U$, так что суффиксную ссылку из $U$ мы проведём в корень, префиксную - в $X$ - и завершим алгоритм.

Второй случай: в какой-то момент мы попали в состояние $P$, из которого уже был переход по $c$. Этот случай сложнее, и он также предполагает два возможных варианта. Обозначим за $Q$ состояние, в которое ведёт переход по символу $c$ из $P$. Пусть самая длинная строка, принимаемая $P$ - это $l$. Снова рассмотрим два случая:

1. Префиксная ссылка из $Q$ ведёт в $P$. Это означает, что состояние $Q$, как и все достижимые по суфф. ссылкам из $Q$ состояния, принимает только суффиксы $sc$: исходя из определения префиксной ссылки, $l$ является самой длинной строкой, принимаемой $Q$, с приписанным в конце символом $c$, то есть суффиксом $sc$, а все остальные строки, принимаемыми $P$, являются суффиксами самой длинной.
2. Префиксная ссылка из $Q$ ведёт не в $P$. Это означает, что существует строка, принимаемая $Q$, длина которой больше, чем $lc$; но такая строка если и является суффиксом $sc$, то из одного из ранее посещённых (в первой части алгоритма) состояний есть переход по $c$ - противоречие; значит, $Q$ помимо суффиксов $sc$ также принимает строки, не являющиеся суффиксами $sc$, что недопустимо. Поэтому мы должны сделать две версии $Q$: одна принимает строки старого $Q$, являющиеся суффиксами $sc$ - назовём их основным набором, а вторая - все остальные строки $Q$ - назовём их дополнительным набором. Для этого клонируем состояние $Q$: создадим новое состояние $Q'$, которое будет отвечать за строки основного набора, скопируем в него все переходы, которые были в $Q$ и скопируем суффиксную ссылку из $Q$. Префиксную ссылку из $Q'$ проведём в $P$. Состояние $Q$ теперь будет отвечать только за строки дополнительного набора, поэтому мы должны перенаправить его суффссылку в $Q'$. Суффиксная ссылка из $U$ также должна указывать на $Q'$, т.к. все суффиксы $sc$ большей длины уже принимаются $U$. Осталось только перенаправить некоторые переходы, ведущие в $Q$, на состояние $Q'$: заметим, что это будут в точности все переходы по $c$ в $Q'$ из всех состояний, достижимых по суффиксным ссылкам из $P$, включая $P$.

Для строки длины 0 суффиксный автомат - это единственное, корневое состояние. Таким образом, мы получили корректный алгоритм построения суффиксного автомата.

Связь между суффиксным автоматом и суффиксным деревом

Рассмотрим ребро в суффиксном дереве строки $T$, а точнее все подстроки $T$, которым соответствует или "внутренняя" вершина ребра, или вершина, в которой ребро заканчивается. Для любой строки $x$ и любой пары строк $a$, $b$ из рассматриваемого множества строк, строки $xa$ и $xb$ являются или не являются префиксами строки $s$ одновременно.

Пусть $|a| < |b|$. Тогда $a$ является предком $b$ в боре, то есть, её префиксом, значит, её множество вхождений точно содержит множество вхождений строки $b$. Допустим, существует позиция $|x|$, в которой есть вхождение строки $a$, но не строки $b$.

Рассмотрим строку $a'$, которая является максимальным префиксом строки $b$, который можно встретить в той позиции. Если $a'$ не упирается в конец строки, то её можно продолжить, как минимум, двумя различными символами чтобы она осталась подстрокой $T$. Значит, соответствующая ей вершина в дереве имеет степень больше двух и должна разбивать ребро, на котором находится, что конфликтует с предположением о том, что $a$ и $b$ взяты с одного ребра.

Если же $a'$ нельзя продолжить, то она всё ещё должна разбивать ребро, т.к. является суффиксом строки и её вершина не будет удалена при сжатии рёбер.

Аналогичным образом можно показать, что для любой строки $a$ все строки $b$ с таким же множеством строк $x$ находятся на соответствующем строке $a$ ребре, то есть, есть биекция между рёбрами суффиксного дерева и множествами левых позиций вхождений строк в $T$. Отсюда:

Для любого состояния $q$ суффиксного автомата строки $T$ найдётся вершина $q'$ суффиксного дерева развернутой строки $T$ такая, что множество строк, принимаемых состоянием $q$, совпадает с развёрнутым множеством строк, таких что соответствующая им вершина в дереве лежит на ребре, ведущем в $q'$ (включая строку, соответствующую $q'$).

Это целиком описывает состояния автомата и позволяет разработать алгоритм его построения. Код суффиксного автомата можно найти в конце статьи.

Время работы

Достаточно очевидно, что вершин в автомате (и, соответственно, префиксных и суффиксных ссылок) не более $2n$ - действительно, для каждого символа добавляется ровно одно состояние и клонируется максимум одно. Переходов, очевидно, не более $nk$, однако можем дать более строгую оценку сверху в $3n$. Сплошных переходов - т.е. ведущих в состояние $X$ из состояния, достижимого по префиксной ссылке $X$ - не более $2n$. Рассмотрим переходы, не являющиеся сплошными. Состояния, принимающие суффиксы строки, назовём терминальными. Каждому из оставшихся переходов поставим в соответствие строку $t_{1}ct_{2}$, где $c$ - символ на ребре, $t_1$ - самая длинная строка, принимаемая "истоком" перехода, а $t_2$ - самая длинная строка, ведущая из "стока" перехода до некоторого терминального состояния. Заметим, что $t_1$ и $t_2$ образованы только сплошными переходами (т.к. если от одного состояния до другого есть некоторый путь, то есть не менее короткий путь, проходящий только по сплошным переходам). Также заметим, что во-первых, полученная строка будет являться некоторым суффиксом исходной, а во-вторых, так как все переходы кроме одного в таком пути сплошные, все такие строки будут различными. Из этих двух фактов следует, что количество несплошных переходов не более $n$, так как у строки ровно $n$ суффиксов. Таким образом, переходов в автомате не более $3n$, а ссылок не более $4n$, то есть автомат линеен по памяти. По сути, доказав асимптотику по памяти, мы почти доказали время работы, и неочевидным остаётся только то, за сколько работает перенаправление переходов после клонирования. Заметим, что если мы добавляли символ $c$ и клонировали состояние $Q$ и получили $Q'$, то не может быть такого, что через какое-то время мы добавим символ $c$ и нам пришлось клонировать $Q'$ и, соответственно, перенаправлять переходы по $c$, ведущие в $Q'$. Доказательство: из $P$ обязательно есть переход по символу $c$ в $Q'$, причём этот переход сплошной, и такие переходы есть только из $P$ и некоторых достижимых из него по суффиксным ссылкам состояний. Также заметим, что для некоторого $k \geq 0$ и только для него из всех состояний, достижимых из $P$ за $k$ переходов по суффиксным ссылкам, будет существовать переход в $Q'$. Таким образом, ни один клон не будет клонирован повторно, а все остальные вершины будут клонированы максимум один раз, то есть каждый переход будет перенаправлен максимум один раз, а переходов линейное число, поэтому суммарно будет совершено $O(n)$ действий для перенаправления. Итак, мы доказали, что суффиксный автомат линеен по памяти и требует $O(n log k)$ времени на построение. TODO доказательство неверное

Применение в решении задач

1. Число различных подстрок. Дана строка $s$, необходимо посчитать

   количество её различных подстрок. В каждом состоянии встречаются

   строки длины от $len(link(q)) + 1$ до $len(q)$. Всего

   $len(q) - len(link(q))$ строк. Просуммировав эту величину по всем

   состояниям, получим ответ.

   Упражнение: решите эту же задачу за $O(n)$, учитывая, что к строке

   $s$ символы дописываются по одному и после каждого нового символа

   необходимо сказать текущее число различных подстрок строки $s$.

   Упражнение*: Возьмём задачу из предыдущего упражнения и скажем,

   что теперь мы можем не только дописывать символы в конец, но и

   удалять их с начала строки. Вам требуется отвечать на те же

   запросы. Время работы решения всё ещё должно линейно зависеть от

   размера входа. Подсказка: иногда алгоритм Укконена также бывает

   полезен.

2. Поиск подстрок в тексте. Пропустив строку через автомат мы

   сможем сказать, входит ли она в текст. Допустим, мы хотим узнать

   какую-то информацию о её вхождениях. Например, нам нужно выдать

   любое конкретное вхождение. Как мы уже знаем, каждому вхождению

   соответствует строка $x$ такая что $ax$ --- суффикс $s$. Или, проще

   говоря, путь из состояния $q$ в какое-то финальное состояние.

   Динамикой по автомату как ациклическому ориентированному графу мы

   можем найти длину какого-нибудь такого пути (например, для

   определённости минимального или максимального). Отметим, что

   аналогичной динамикой считаются многие другие полезные значения,

   например, количество строк в правом контексте состояния (или, что то

   же самое, количество вхождений строк из состояния в $s$).

   Альтернативным решением будет обратиться к дереву суффиксных ссылок,

   которое, как мы помним, является суффиксным деревом для $s^T$. Как

   мы упоминали в самом начале, любая подстрока строки $s$ является

   префиксом одного из суффиксов исходной строки. Таким образом, если

   мы запишем в каждую "суффиксную" вершину индекс соответствующего ей

   суффикса, то все позиции вхождений строки $t$ в $s$ можно будет

   обнаружить в поддереве вершины, которая соответствует строке $t$.

   Значит, в частности, динамикой можно будет найти самое первое или

   самое последнее вхождение.

   Более того, учитывая, что в последнем случае мы работали с деревом,

   мы можем обойти его таким образом, чтобы на каждом шаге иметь в

   вершине множество возможных позиций, в которых встречаются строки из

   соответствующего состояния. Для этого нужно применить идею быстрого

   слияния множеств, когда мы всегда добавляем элементы из меньшего

   множества в большее, а не наоборот. Тогда такой обход потребует

   $O(n \log n)$ операций добавления в множество, т.к. каждый раз когда

   мы переносим между множествами элемент $k$, размер нового множества

   будет как минимум, в два раза больше старого, в котором он хранился.

   Упражнение*: дана строка $s$. Найти число строк $t$ таких, что

   они имеют хотя бы $3$ непересекающихся вхождения в строку $s$.

3. Наибольшая общая подстрока. Нам дано $k$ строк

   $s_1, s_2, \dots, s_k$. Нужно найти наибольшую строку $t$, которая

   встречается в каждой из строк $s_i$. Одно из возможных решений ---

   построить автомат для строки $s_1 t_1 s_2 t_2 \dots s_n t_n$, где

   $t_i$ --- уникальный для каждой строки символ-разделитель. Теперь мы

   можем завести динамику $dp[q][i]$, в которой хранить $1$, если из

   состояния $q$ можно добраться до состояния, из которого есть переход

   по $t_i$, не проходя при этом через другие символы-разделители. Это

   будет равносильно тому, что строки из $q$ входят в $s_i$. Как и в

   прошлый раз, динамику можно пересчитывать по топологической

   сортировке автомата как ориентированного ациклического графа. Итого

   решение будет работать за $O(k \cdot \sum |s_i|)$.

   Упражнение*: решить указанную задачу за $O(\sum |s_i|)$.

   Модификация суффиксного автомата

   Эта модификация была придумана и рассказана Филиппом Грибовым, в частности, в рамках программы третьего курса кружка по алгоритмам Tinkoff Generation (2018-2019). Суть заключается в следующем: заметим, что при построении и доказательстве асимптотики на самом деле мы никак не использовали, что строится автомат только для одной строки. То есть после того, как мы построили суффиксный автомат по некоторой строке, мы можем сказать, что вершина, принимающая всю строку (last) - это корень автомата, и спокойно добавить в автомат вторую строку, и после этого автомат будет принимать все различные подстроки как первой, так и второй строк. Очевидно, можно так же построить автомат и для трёх, четырёх и т.д. строк, что даёт нам просто решать такие сложные задачи, как следующая:

Дан словарь строк, изначально пустой. Приходят запросы трёх типов: добавить строку в словарь, если её нет, удалить строку из словаря, если она есть, и найти суммарное количество вхождений строк словаря в заданный текст. Задача в онлайн.

Сперва введём вспомогательное понятие. Подавтоматом состояния $U$ суффиксного автомата называется такой его подграф, что в нём есть пути по всем подстрокам самой длинной принимаемой $U$ строки и только по ним. Обойти подавтомат можно простой рекурсивной функцией типа DFS: по сути, для этого нам нужно пройтись по всем суффиксам всех префиксов (или наоборот) данной строки, то есть если мы находимся в состоянии $X$, то мы либо ничего не делаем, если $X$ уже была посещена этим обходом, либо запускаем функцию сначала от вершины, достижимой по префиксной ссылке, а затем по суффиксной. Теперь можно перейти к решению задачи. Для обработки запроса первого типа просто добавим строку в суффиксный автомат и пометим последнюю вершину как терминальную, т.е. отвечающую за одну из строк. Для обработки запроса второго типа найдём вершину, отвечающую за данную строку, и если она есть, просто снимем терминальную пометку. Для обработки запроса третьего типа добавим заданную строку в суффиксный автомат и пройдёмся по её подавтомату, при этом запоминая для каждой вершины количество вершин с терминальной меткой в её подавтомате. Тогда если мы попали в уже посещённую во время обхода подавтомата вершину, то просто прибавим уже посчитанный для неё ответ. Осталось только понять асимптотику, ведь если в автомате есть несколько строк, то может случиться так, что у некоторых размер подавтомата будет порядка квадрата от их длины. Пусть суммарная длина всех строк запросов это $m$. Давайте разделим строки на тяжёлые (длина больше $\sqrt{m}$) и лёгкие (длина не больше $\sqrt{m}$). тяжёлых строк не больше $\sqrt{m}$, и при этом размер подавтомата любой строки не больше $O(m)$, поэтому суммарное время обработки тяжёлых строк не больше $O(m \sqrt{m}). Лёгких строк может быть много, и размер подавтомата строки длиной $l$ может быть $O(l^2)$, что не больше, чем $O(\sqrt{m})$; суммарная длина всех строк не больше $m$, а значит суммарное время на обработку всех лёгких строк также порядка $O(m \sqrt{m})$. Таким образом, мы получили довольно простое решение такой задачи за $O(m \sqrt{m})$ с небольшой константой, которое заходит даже для $m$ порядка $10^6$. И таким образом можно строить не только суффиксный автомат по нескольким строкам: можно "подвешивать" одну строку к другой и т.д.

Реализация

struct node {
  int link = -1, p = -1, len = 0; // Суффиксная, префиксная ссылки и максимальная длина принимаемой состоянием строки, соответственно
  char pc = '#'; // Символы, переходы по которым ведут в состояние
  map<char, int> next; // Переходы по символам

  node() {}

  node(int p, int len, char pc) : p(p), len(len), pc(pc) {}
};

node v[2 * MAXN]; // MAXN - максимально возможная суммарная длина строк
int mx = 0; // номер последнего добавленного состояния

int add_char(int ls, char c) { // ls - состояние, к которому мы "подвешиваем" следующий символ, c - сам символ
  if (v[ls].next.find(c) != v[ls].end()) return v[ls].next[c]; // Если переход по символу c из ls уже был, то ничего добавлять не надо
  v[++mx] = node(ls, v[ls].len + 1, c);
  int p = ls;
  for (; p != -1 && v[p].next.find(c) == v[p].end(); p = v[p].link)
      v[p].next[c] = mx;
  if (p == -1) {
      v[mx].link = 0; // Если перехода по c не нашлось
      return mx;
  }
  int q = v[p].next[c];
  if (v[q].p == p) {
      v[mx].link = q;
      return mx;
  }
  v[++mx] = node(p, v[p].len + 1, c); // Клонирование
  v[mx].next = v[q].next; v[mx].link = v[q].link;
  v[q].link = v[mx - 1].link = mx;
  for (; p != -1 && v[p].next[c] == q; p = v[p].link)
      v[p].next[c] = mx;
  return mx - 1;
}

int used[MAXN * 2]; // Массив времён посещения обходом подавтомата

void subautomaton(int x, int tm) { // Обход подавтомата
  if (x == -1 || used[x] == tm) return;

  used[x] = tm;
  //....

  subautomaton(v[x].p, tm);
  subautomaton(v[x].link, tm);
}