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

Суффиксный автомат
англ. Suffix automaton
Суффиксный автомат для abbcbc
Тип	Индекс подстрок
Год изобретения	1983
Автор	Ансельм Блумер[вд], Джанет Блумер[вд], Анджей Эренфехт[вд], Дэвид Хаусслер[вд] и Росс МакКоннелл[вд]
Сложность в О-символике
В худшем случае Построение $O(\vert S\vert \log \vert \Sigma \vert )$ Расход памяти $O(\vert S\vert )$
Медиафайлы на Викискладе

Суффиксный автомат (англ. suffix automaton, directed acyclic word graph, DAWG) — детерминированный конечный автомат (ДКА), принимающий все суффиксы слова $S=s_{1}s_{2}\dots s_{n}$ и только их, и обладающий наименьшим возможным числом состояний среди всех таких автоматов. Суффиксный автомат был впервые описан группой учёных из Денверского и Колорадского университетов в 1983 году, они же показали, что размер автомата линейно зависит от длины $S$, а также предложили онлайн-алгоритм для его построения с линейным временем работы.

В дальнейших работах на эту тему была обнаружена тесная связь суффиксного автомата с суффиксными деревьями, а сама концепция суффиксного автомата получила различные обобщения. Так были введены сжатый суффиксный автомат, получаемый из исходного процедурой, аналогичной той, которая применяется к суффиксному бору для получения суффиксного дерева, а также обобщённый суффиксный автомат, который строится для набора слов $S_{1},S_{2},\dots ,S_{k}$ и принимает слова, являющиеся суффиксами хотя бы одного из данных.

С помощью суффиксного автомата можно эффективно решать такие задачи как поиск подстроки в строке, определение наибольшей общей подстроки двух и более строк и другие.

История

Дэвид Хаусслер

Ансельм Блумер, на доске изображён CDAWG для строк ababc и abcab

Концепция суффиксного автомата была представлена группой учёных из Денверского и Колорадского университетов Ансельмом Блумером, Анджеем Эренфехтом, Дэвидом Хаусслером, Россом МакКоннеллом и Джанет Блумер в 1983 году, хотя связанные с ним структуры встречались ранее в работах Питера Вайнера, Вона Пратта и Анатолия Олесьевича Слисенко, посвящённых алгоритмам построения суффиксных деревьев. В той же работе Блумер и другие показали, что построенный по слову $S$ длины больше $1$ автомат содержит не больше $2|S|-1$ состояний и не больше $3|S|-4$ переходов, а также привели линейный алгоритм построения автомата.

В 1983 году М. Т. Чен и Джоэл Сейферас независимо разработали алгоритм построения суффиксного автомата, показывающий, что алгоритм Вайнера, предложенный в 1973 году для построения суффиксного дерева слова $S$, также строит суффиксный автомат для обращённого слова ${\textstyle S^{R}}$ в качестве вспомогательной структуры. В 1987 году Блумер и другие, по аналогии с суффиксным деревом, описали сжатый суффикный автомат (англ. compact directed acyclic word graph, CDAWG), получаемый из суффиксного автомата удалением нефинальных состояний с полустепенью исхода, равной единице, а в 1997 году Максим Крошемор и Рено Верин разработали линейный алгоритм для его прямого построения. В 2001 году Шунсуке Иненага и другие разработали линейный онлайн-алгоритм для построения сжатого суффиксного автомата, а также линейный алгоритм для построения сжатого суффиксного автомата для набора слов, заданного префиксным деревом.

Основные обозначения

При описании суффиксных автоматов и связанных с ними фактов и теорем часто используются обозначения из теории формальных языков в целом и теории автоматов в частности:

• Алфавит — конечное множество $\Sigma$, из которого могут состоять слова. Его элементы называются символами;
• Слово — конечная последовательность символов алфавита: $\omega =\omega _{1}\omega _{2}\dots \omega _{n}$, где $\omega _{k}\in \Sigma$ для $k=1..n$. Длина слова $\omega$ обозначается как $|\omega |=n$;
• Формальный язык — некоторое множество слов над заданным алфавитом;
• Язык всех слов обозначается как $\Sigma ^{*}$(здесь символ «*» несёт смысл звезды Клини), пустое слово (слово нулевой длины) — символом $\varepsilon$;
• Конкатенация (произведение) слов $\alpha =\alpha _{1}\alpha _{2}\dots \alpha _{n}$ и $\beta =\beta _{1}\beta _{2}\dots \beta _{m}$ обозначается как $\alpha \cdot \beta$ или $\alpha \beta$ и равна слову, получаемому приписыванием $\beta$ к $\alpha$ справа, то есть, $\alpha \beta =\alpha _{1}\alpha _{2}\dots \alpha _{n}\beta _{1}\beta _{2}\dots \beta _{m}$;
• Конкатенация языков $A$ и $B$ обозначается как $A\cdot B$ или $AB$ и равна множеству попарных конкатенаций $AB=\{\alpha \beta :\alpha \in A,\beta \in B\}$;
• Если слово $\omega \in \Sigma$ представимо в виде $\omega =\alpha \gamma \beta$, где $\alpha ,\beta ,\gamma \in \Sigma ^{*}$, то слова $\alpha$, $\beta$ и $\gamma$ называют префиксом, суффиксом и подсловом (подстрокой) слова $\omega$ соответственно;

Структура автомата

Как и любой конечный автомат, суффиксный автомат, заданный формальной пятёркой ${\mathcal {A}}=(\Sigma ,Q,q_{0},F,\delta )$, может быть представлен в виде ориентированного графа (диаграммы) такого что:

• Множество вершин графа соответствует множеству состояний автомата $Q$,
• В графе выделена некоторая вершина, соответствующая начальному состоянию $q_{0}\in Q$,
• В графе выделен набор вершин, соответствующих множеству финальных состояний $F\subset Q$,
• Множество дуг в графе соответствует множеству переходов $\delta \subset Q\times \Sigma \times Q$, которое состоит из троек $(q_{1},\sigma ,q_{2})$, где $q_{1},q_{2}\in Q$ и $\sigma \in \Sigma$ (см. декартово произведение),
• При этом переходу ${\textstyle (q_{1},\sigma ,q_{2})\in \delta }$ соответствует дуга из $q_{1}$ в $q_{2}$, помеченная символом алфавита $\sigma$. Такой переход также обозначают как ${\textstyle q_{1}{\begin{smallmatrix}{\sigma }\\[-5pt]{\longrightarrow }\end{smallmatrix}}q_{2}}$.

В таком графе вершины и дуги отождествляются с состояниями и переходами автомата соответственно. Автомат принимает слово $\omega =\omega _{1}\omega _{2}\dots \omega _{m}$ в том и только том случае, если существует путь из начального состояния $q_{0}$ в некоторое финальное состояние $q\in F$, такой что если сконкатенировать символы, встретившиеся на этом пути, то получится слово $\omega$.

Состояния автомата

Основная статья: Минимизация ДКА

Правым контекстом слова $\omega$ относительно языка $L$ называют множество $[\omega ]_{R}=\{\alpha :\omega \alpha \in L\}$. То есть это множество слов $\alpha$, при приписывании которых к слову $\omega$ справа получается слово из языка $L$. Правые контексты индуцируют естественное отношение эквивалентности $[\alpha ]_{R}=[\beta ]_{R}$ на множестве всех слов. В терминах правых контекстов можно записать важное утверждение о минимальных автоматах, следующее из теоремы Майхилла — Нероуда:

Минимальный автомат, распознающий язык $L$ над алфавитом $\Sigma$, может быть задан в явном виде:

• Алфавит $\Sigma$ остаётся без изменений,
• Состояниям $Q$ соответствуют правые контексты $[\omega ]_{R}$ всех слов $\omega \in \Sigma ^{*}$,
• Начальному состоянию $q_{0}$ соответствует правый контекст пустого слова $[\varepsilon ]_{R}$,
• Финальным состояниям $F$ соответствуют правые контексты $[\omega ]_{R}$ слов из языка $\omega \in L$,
• Переходы $\delta$ имеют вид $[\omega ]_{R}{\begin{smallmatrix}{\sigma }\\[-5pt]{\longrightarrow }\end{smallmatrix}}[\omega \sigma ]_{R}$, где $\omega \in \Sigma ^{*}$ и $\sigma \in \Sigma$.

Полученный таким образом минимальный автомат определён однозначно с точностью до изоморфизма.

В случае суффиксного автомата язык $L$ состоит из суффиксов слова $S=s_{1}s_{2}\dots s_{n}$, поэтому правый контекст слова $\omega$ состоит из слов $\alpha$ таких что $\omega \alpha$ — суффикс $S$. Это позволяет сформулировать следующую лемму:

Пусть $endpos(\omega )=\{r:\omega =s_{l}\dots s_{r}\}$ — множество правых концов вхождений $\omega$ в $S$.

Между элементами множеств $endpos(\omega )$ и $[\omega ]_{R}$ есть следующее взаимно однозначное соответствие:

• Если $x\in endpos(\omega )$, то $s_{x+1}s_{x+2}\dots s_{n}\in [\omega ]_{R}$;
• Если $\alpha \in [\omega ]_{R}$, то $n-\vert \alpha \vert \in endpos(\omega )$.

Из этого следует ряд структурных свойств состояний суффиксного автомата и слов, которые ими принимаются. Пусть $|\alpha |\leq |\beta |$, тогда:

• Если у $[\alpha ]_{R}$ и $[\beta ]_{R}$ есть хотя бы один общий элемент $x$, то $\alpha$ — суффикс $\beta$ и, как следствие, $endpos(\beta )\subset endpos(\alpha )$ и $[\beta ]_{R}\subset [\alpha ]_{R}$;
• Если $[\alpha ]_{R}=[\beta ]_{R}$, то $endpos(\alpha )=endpos(\beta )$, то есть $\alpha$ встречается в $S$ только в качестве суффикса $\beta$;
• Если $[\alpha ]_{R}=[\beta ]_{R}$ и $\gamma$ — суффикс $\beta$, такой что $|\alpha |\leq |\gamma |\leq |\beta |$, то $[\alpha ]_{R}=[\gamma ]_{R}=[\beta ]_{R}$.

Таким образом, любое состояние $q=[\alpha ]_{R}$ суффиксного автомата принимает некоторую непрерывную цепочку вложенных друг в друга суффиксов наибольшей строки из этого состояния.

Левым расширением ${\overset {\scriptstyle {\leftarrow }}{\gamma }}$ строки $\gamma$ называют самую длинную строку $\omega$, имеющую тот же правый контекст, что и $\gamma$. Длину $|{\overset {\scriptstyle {\leftarrow }}{\gamma }}|$ самой длинной строки, принимаемой состоянием $q=[\gamma ]_{R}$, обозначают как $len(q)$. Для него верно, что:

Левое расширение строки $\gamma$ может быть представлено в виде ${\overleftarrow {\gamma }}=\beta \gamma$, где $\beta$ — самое длинное слово, такое что любому вхождению слова $\gamma$ в $S$ предшествует слово $\beta$.

Cуффиксной ссылкой $link(q)$ от состояния $q=[\alpha ]_{R}$ называют указатель на состояние $p$, содержащее наибольший суффикс $\alpha$, который не принимается состоянием $q$.

В таких обозначениях можно сказать, что состояние $q=[\alpha ]_{R}$ принимает в точности все суффиксы ${\overset {\scriptstyle {\leftarrow }}{\alpha }}$, которые длиннее $len(link(q))$ и не длиннее $len(q)$. Кроме того, верно следующее:

Суффиксные ссылки образуют дерево ${\mathcal {T}}(V,E)$, которое можно задать явно следующим образом:

1. Вершинам $V$ соответствуют левые расширения ${\overleftarrow {\omega }}$ всех подстрок $S$,
2. Рёбра $E$ соединяют вершины $({\overleftarrow {\omega }},{\overleftarrow {\alpha \omega }})$ такие что $\alpha \in \Sigma$ и ${\overleftarrow {\omega }}\neq {\overleftarrow {\alpha \omega }}$.

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

Преобразования суффиксных структур

Основная статья: Суффиксное дерево

По определению, суффиксный автомат может быть получен минимизацией суффиксного бора. Кроме того, сжатый суффиксный автомат может быть получен как минимизацией суффиксного дерева, так и сжатием обычного автомата. Однако, помимо очевидной связи между суффиксным автоматом и суффиксным деревом одной и той же строки, можно также установить некоторое соответствие между суффиксным автоматом строки $S=s_{1}s_{2}\dots s_{n}$ и суффиксным деревом обращённой строки $S^{R}=s_{n}s_{n-1}\dots s_{1}$. Аналогично правым контекстам можно ввести левые контексты $[\omega ]_{L}=\{\beta \in \Sigma ^{*}:\beta \omega \in L\}$ и правые расширения ${\overset {\scriptstyle {\rightarrow }}{\omega ~}}$, соответствующие самым длинным строкам, имеющим заданный левый контекст, а также отношение эквивалентности $[\alpha ]_{L}=[\beta ]_{L}$. Если рассматривать правые расширения относительно языка $L$ префиксов строки $S$, то можно получить, что:

Суффиксное дерево строки $S$ может быть задано в явном виде следующим образом:

• Вершинам $V$ соответствуют правые расширения ${\overrightarrow {\omega }}$ всех подстрок $S$,
• Рёбрам $E$ соответствуют тройки $({\overrightarrow {\omega }},x\alpha ,{\overrightarrow {\omega x}})$ такие что $x\in \Sigma$ и ${\overrightarrow {\omega x}}={\overrightarrow {\omega }}x\alpha$.

Здесь тройка $(v_{1},\omega ,v_{2})\in E$ значит, что на ребре из $v_{1}$ в $v_{2}$ записана строка $\omega$.

Из чего следует, что дерево суффиксных ссылок для автомата строки $S$ и суффиксное дерево строки $S^{R}$ изоморфны:

• Связь суффиксных структур
• 
  Суффиксный автомат для строки abbcbc
• 
  Суффиксный бор, суффиксное дерево и CDAWG для строки abbcbc. Номера вершин соответствуют состояниям, в которые они переходят при минимизации или сжатии
• 
  Суффиксное дерево для строки cbcbba
  (дерево суффиксных ссылок для автомата строки abbcbc)

Аналогично левым расширениям, для правых расширений также может быть сформулирована структурная лемма:

Правое расширение строки $\gamma$ может быть представлено в виде ${\overrightarrow {\gamma }}=\gamma \alpha$, где $\alpha$ — самое длинное слово, такое что за любым вхождением $\gamma$ в $S$ сразу следует слово $\beta$.

Размер

В суффиксном автомате строки $S$ длины $n>1$ не больше $2n-1$ состояний и не больше $3n-4$ переходов, причём данные оценки достигаются на строках $abb\dots bb=ab^{n-1}$ и $abb\dots bc=ab^{n-2}c$ соответственно. Можно также сформулировать более сильное утверждение о связи числа состояний и переходов в автомате: $|\delta |\leq |Q|+n-2$, где $|\delta |$ и $|Q|$ — это число переходов и состояний соответственно.

• Максимальные суффиксные автоматы
• 
  Суффиксный автомат для $ab^{n-1}$
• 
  Суффиксный автомат для $ab^{n-2}c$

Построение

Суффиксный автомат строки $S=s_{1}s_{2}\dots s_{n}$ строится последовательным наращиванием слова, для которого он построен. Изначально имеется тривиальный автомат, построенный для пустого слова, а затем на каждом шаге к текущему слову добавляется один символ, что влечёт за собой перестройку состояний и переходов автомата.

Изменение состояний

Добавление суффикса cbcbba к суффиксному дереву слова bcbba. В суффиксном автомате слова abbcbc вершина 7 соответствует всему слову, а вершина 8 отщепляется от вершины 5 и становится общей суффиксной ссылкой для вершин 5 и 7.

После приписывания нового символа к слову, некоторые классы эквивалентности изменятся. Пусть $[\alpha ]_{R_{\omega }}$ — правый контекст слова $\alpha$ относительно языка суффиксов слова $\omega$. Тогда переход от $[\alpha ]_{R_{\omega }}$ к $[\alpha ]_{R_{\omega x}}$ при приписывании символа $x$ к слову $\omega$ описывается следующей леммой:

Пусть $\alpha ,\omega \in \Sigma ^{*}$ — некоторые слова над алфавитом $\Sigma$ и $x\in \Sigma$ — некоторый символ этого алфавита. Тогда между правыми контекстами $[\alpha ]_{R_{\omega }}$ и $[\alpha ]_{R_{\omega x}}$ слова $\alpha$ относительно языков суффиксов слов $\omega$ и $\omega x$ соответственно имеет место следующая связь:

• $[\alpha ]_{R_{\omega x}}=[\alpha ]_{R_{\omega }}x\cup \{\varepsilon \}$ если $\alpha$ — суффикс $\omega x$;
• $[\alpha ]_{R_{\omega x}}=[\alpha ]_{R_{\omega }}x$ в противном случае.

То есть при добавлении одного символа $x$ к текущему слову $\omega$ правый контекст слова $\alpha$ может измениться только в том случае, если $\alpha$ является суффиксом слова $\omega x$. Из этого следует, что разбиение всех слов на классы эквивалентности по $\equiv _{R_{\omega x}}$ является измельчением разбиения на классы эквивалентности по $\equiv _{R_{\omega }}$. Другими словами, если $[\alpha ]_{R_{\omega x}}=[\beta ]_{R_{\omega x}}$, то $[\alpha ]_{R_{\omega }}=[\beta ]_{R_{\omega }}$. Кроме того, при добавлении очередного символа к слову расщепление произойдёт у не более чем двух состояний. В первую очередь будет расщеплено состояние, которому соответствует пустой правый контекст (то есть то, которое принимает язык слов, не входящих в $\omega$ в качестве подслова). Из этого состояния будет выделено новое состояние, содержащее всё слово $\omega x$, а также все его суффиксы, которые встречаются в $\omega x$, но не встречались в $\omega$. Соответственно, правый контекст этих слов, который ранее был пустым, теперь будет состоять только из пустого слова.

Учитывая связь между состояниями суффиксного автомата и вершинами суффиксного дерева, можно отследить и второе состояние, которое может расщепиться при добавлении очередного символа. Так как переход от слова $\omega$ к $\omega x$ соответствует переходу от $\omega ^{R}$ к $x\omega ^{R}$ для обращённой строки, приписывание символа $x$ к строке $\omega$ соответствует внесению одного нового (самого длинного) суффикса $x\omega ^{R}$ в суффиксное дерево строки $\omega ^{R}$. При этом появляется не более двух вершин: одна из них будет соответствовать всему слову $x\omega ^{R}$, а другая может появиться в том месте, где происходит ответвление от дерева. Таким образом, одно новое состояние соответствует правому контексту всей строки $\omega x$, а другое (если оно есть) может соответствовать только суффиксной ссылке этого состояния. Данные наблюдения можно обобщить теоремой:

Пусть $\omega \in \Sigma ^{*}$ и $x\in \Sigma$. Пусть также $\alpha$ является самым длинным суффиксом $\omega x$, который встречается в $\omega$, а $\beta ={\overset {\scriptstyle {\leftarrow }}{\alpha }}$ — его левое расширение относительно $\omega$, то есть самое длинное подслово слова $\omega$ такое что $[\alpha ]_{R_{\omega }}=[\beta ]_{R_{\omega }}$. Тогда для любых подслов $u,v$ слова $\omega$ верно следующее:

• Если $[u]_{R_{\omega }}=[v]_{R_{\omega }}$ и $[u]_{R_{\omega }}\neq [\alpha ]_{R_{\omega }}$, то $[u]_{R_{\omega x}}=[v]_{R_{\omega x}}$;
• Если $[u]_{R_{\omega }}=[\alpha ]_{R_{\omega }}$ и $\vert u\vert \leq \vert \alpha \vert$, то $[u]_{R_{\omega x}}=[\alpha ]_{R_{\omega x}}$;
• Если $[u]_{R_{\omega }}=[\alpha ]_{R_{\omega }}$ и $\vert u\vert >\vert \alpha \vert$, то $[u]_{R_{\omega x}}=[\beta ]_{R_{\omega x}}$.

В частности, если $\alpha =\beta$ (например, когда $x$ вообще не встречается в $\omega$ и $\alpha =\beta =\varepsilon$), расщепления второго состояния не происходит.

Помимо суффиксных ссылок, в новом автомате также нужно определить финальные состояния. Из структурных свойств автомата следует, что суффиксы любого слова $\alpha$ расположены таким образом, что если $q=[\alpha ]_{R}$, то суффиксы $\alpha$, чья длина превышает $len(link(q))$, лежат в $q$, суффиксы, чья длина больше $len(link(link(q))$, но не больше $len(link(q))$, лежат в $link(q)$ и так далее. Иными словами, для любого суффикса $\alpha$ найдётся вершина в суффиксном пути состояния $q$, который задаётся последовательностью $(q,link(q),link^{2}(q),\dots )$. Соответственно если обозначить состояние, принимающее в текущий момент всю строку $\omega$, как $last$, то терминальными (принимающими суффиксы $\omega$) состояниями будут те и только те состояния, которые входят в суффиксный путь $(last,link(last),link^{2}(last),\dots )$.

Изменение переходов и суффиксных ссылок

Какие-либо изменения при добавлении очередного символа затрагивают не более чем два новых состояния, поэтому изменения в переходах автомата тоже будут затрагивать только эти состояния. После приписывания $x$ к слову $\omega$ образуется новое состояние $[\omega x]_{R_{\omega x}}$, а также, возможно, состояние $[\alpha ]_{R_{\omega x}}$. Суффиксная ссылка из $[\omega x]_{R_{\omega x}}$ будет вести в $[\alpha ]_{R_{\omega x}}$, а из $[\alpha ]_{R_{\omega x}}$ — в $link([\alpha ]_{R_{\omega }})$. Слова из $[\omega x]_{R_{\omega x}}$ встречаются в $\omega x$ только в виде суффиксов, поэтому из $[\omega x]_{R_{\omega x}}$ не должно быть переходов, а ведущие в него переходы должны вести по символу $x$ из суффиксов $\omega$ с длиной хотя бы $|\alpha |$. Состояние $[\alpha ]_{R_{\omega x}}$ отщепляется от $[\alpha ]_{R_{\omega }}$, поэтому переходы из этого состояния будут дублировать таковые у $[\alpha ]_{R_{\omega }}$. А ведущие в него переходы будут вести по символу $x$ из состояний, соответствующим суффиксам $\omega$ длины меньше $|\alpha |$ и не меньше $len(link([\alpha ]_{R_{\omega }}))$, так как ранее эти переходы вели в $[\alpha ]_{R_{\omega }}$ и соответствовали отделившейся части состояния. Состояния, принимающие данные слова, можно определить по суффиксному пути состояния $[\omega ]_{R_{\omega }}$.

Алгоритм

Теоретические результаты выше приводят к следующему алгоритму:

1. Поддерживается номер состояния $last$, соответствующего всей строке $\omega$;
2. При добавлении очередного символа $x$, номер $last$ запоминается в переменной $p$, а в $last$ записывается номер нового состояния, соответствующего слову $\omega x$;
3. Из состояний, соответствующих суффиксам $\omega$, проставляются переходы в $last$. Для этого идёт обход суффиксного пути $p,link(p),link^{2}(p),\dots$, пока не встретится состояние, из которого уже есть переход по $x$;
4. Дальнейшие действия соответствуют одному из трёх случаев:
   1. Если на всём суффиксном пути ни из одного состояния нет перехода по $x$, то $x$ раньше не встречался в $\omega$ и суффиксная ссылка из $last$ ведёт в $q_{0}$;
   2. Если переход по $x$ нашёлся и ведёт из состояния $p$ в состояние $q$, такое что $len(p)+1=len(q)$, то необходимости расщеплять $q$ нет и достаточно провести суффиксную ссылку из $last$ в $q$;
   3. Если же $len(q)>len(p)+1$, то слова из состояния $q$, чья длина не превосходит $len(p)+1$ должны быть выделены в отдельное состояние $cl$;
5. Если на прошлом шаге было выделено отдельное состояние $cl$, то переходы и суффиксная ссылка из него должны дублировать оные в $q$, при этом $cl$ станет общей суффиксной ссылкой состояний $q$ и $last$;
6. Переходы, которые вели в $q$, но соответствовали словам длины не больше $len(p)+1$, следует перенаправить в $cl$. Для этого можно продолжать идти по суффиксному пути $p$, пока не найдётся состояние, переход из которого ведёт не в $cl$.

Возможная реализация этого алгоритма на C++:

const int maxn = ...;    // Максимальное число состояний
map<char, int> to[maxn]; // Переходы
int link[maxn];          // Суффиксные ссылки
int len[maxn];           // Длины максимальных строк в состояниях
int last = 0;            // Состояние, соответствующее всей строке
int sz = 1;              // Общее число состояний

void add_letter(char x) { // К строке w добавляется символ c
    int p = last; // В p записывается состояние строки s
    last = sz++; // Новое состояние для строки wx
    len[last] = len[p] + 1;
    for(; to[p][x] == 0; p = link[p]) {
    	to[p][x] = last; // Создаются переходы в новое состояние
    }
    int q = to[p][x]; 
    if(q == last) { // Символ x раньше не встречался в строке
        link[last] = 0;
    } else if(len[q] == len[p] + 1) { // Расщепления не происходит
    	link[last] = q;
    } else { // От q отщепляется новое состояние
        int cl = sz++; 
        to[cl] = to[q];
        link[cl] = link[q]; 
        len[cl] = len[p] + 1; 
        link[last] = link[q] = cl;
        for(; to[p][x] == q; p = link[p]) {
        	to[p][x] = cl; // Часть переходов перенаправляются из q в cl
        }
    }
}

Вычислительная сложность

В зависимости от используемых структур, детерминированная версия описанного выше алгоритма может быть реализована за время $O(n\log |\Sigma |)$ с $O(n)$ памяти или за время $O(n)$ с $O(n|\Sigma |)$ памяти, если считать, что выделение памяти происходит за $O(1)$. При этом для получения такой оценки времени работы необходимо провести амортизационный анализ внутренних циклов алгоритма. Если рассмотреть, как меняется параметр $len(p)$ после первой итерации первого цикла, то можно увидеть, что с каждой итерацией цикла он строго уменьшается. При этом если на последней итерации предыдущего шага эта величина была равна $k$, то на второй итерации на следующем шаге эта величина будет равна $k+1$. То, что $len(p)$ ни в какой момент времени не превосходит $n$ и что между циклами эта величина увеличивается только на единицу, даёт требуемое утверждение. Аналогичным анализом может быть показана линейность суммарного времени исполнения второго цикла алгоритма.

Вариации и обобщения

Суффиксный автомат тесно связан с другими суффиксными структурами и индексами подстрок. Имея суффиксный автомат некоторой строки, возможно сжатием и рекурсивным обходом данного автомата построить суффиксное дерево этой строки за линейное время. Аналогичные преобразования в обе стороны возможны между суффиксным автоматом строки $S$ и суффиксным деревом обращённой строки $S^{R}$. Помимо этого был разработан ряд модификаций алгоритма, позволяющих строить автомат для множества строк, заданных префиксным деревом, применять к нему сжатие, поддерживать его структуру в режиме скользящего окна, а также перестраивать при удалении или добавлении символов как с конца, так и с начала строки.

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

Как было сказано выше, сжатый суффиксный автомат может быть получен из обычного суффиксного автомата сжатием (удалением состояний, которые не являются финальными и из которых ведёт ровно один переход), а также минимизацией суффиксного дерева, если считать, что алфавит образуют слова, записанные на рёбрах дерева. Кроме того, состояния сжатого автомата могут быть описаны явно, аналогично тому, как это было сделано для несжатого автомата. Двусторонним расширением ${\overset {\scriptstyle {\longleftrightarrow }}{\gamma }}$ слова $\gamma$ называют самое длинное слово $\omega =\beta \gamma \alpha$, такое что любому вхождение $\gamma$ в $S$ предшествует слово $\beta$, а сразу за ним следует слово $\alpha$. В терминах левых и правых расширений это значит, что двустороннее расширение является левым расширением от правого расширения или, что эквивалентно, правым расширением от левого расширения: ${\textstyle {\overset {\scriptstyle \longleftrightarrow }{\gamma }}={\overset {\scriptstyle \leftarrow }{\overset {\rightarrow }{\gamma }}}={\overset {\rightarrow }{\overset {\scriptstyle \leftarrow }{\gamma }}}}$. В терминах двусторонних расширений сжатый суффиксный автомат можно описать следующим образом:

Сжатый суффиксный автомат слова $S$ может быть задан парой $(V,E)$, где:

• $V=\{{\overleftrightarrow {\omega }}:\omega \in \Sigma ^{*}\}$ — множество состояний автомата;
• $E=\{({\overleftrightarrow {\omega }},x\alpha ,{\overleftrightarrow {\omega x}}):x\in \Sigma ,\alpha \in \Sigma ^{*},{\overleftrightarrow {\omega x}}={\overleftrightarrow {\omega }}x\alpha \}$ — множество переходов автомата.

Двусторонние расширения порождают отношение эквивалентности ${\textstyle {\overset {\scriptstyle \longleftrightarrow }{\alpha }}={\overset {\scriptstyle \longleftrightarrow }{\beta }}}$, описывающее слова, принимаемые одним и тем же состоянием сжатого автомата. Это отношение является транзитивным замыканием отношения ${\textstyle ({\overset {\scriptstyle {\rightarrow }}{\alpha \,}}={\overset {\scriptstyle {\rightarrow }}{\beta \,}})\vee ({\overset {\scriptstyle {\leftarrow }}{\alpha }}={\overset {\scriptstyle {\leftarrow }}{\beta }})}$, что подчёркивает тот факт, что состояния сжатого суффиксного автомата могут быть получены как склеиванием вершин суффиксного дерева, эквивалентных по ${\overset {\scriptstyle {\leftarrow }}{\alpha }}={\overset {\scriptstyle {\leftarrow }}{\beta }}$ (минимизация суффиксного дерева), так и склеиванием состояний суффиксного автомата, эквивалентных по ${\overset {\scriptstyle {\rightarrow }}{\alpha \,}}={\overset {\scriptstyle {\rightarrow }}{\beta \,}}$ (сжатие суффиксного автомата). Если у слов $\alpha$ и $\beta$ совпадают правые расширения, а у слов $\beta$ и $\gamma$ — левые, то в совокупности у слов $\alpha$, $\beta$ и $\gamma$ совпадает двустороннее расширение. При этом может оказаться, что у слов $\alpha$ и $\gamma$ не совпадают ни левые, ни правые расширения. В случае $S=\beta =ab$, $\alpha =a$ и $\gamma =b$ левые и правые расширения таковы: ${\overset {\scriptstyle {\rightarrow }}{\alpha \,}}={\overset {\scriptstyle {\rightarrow }}{\beta \,}}=ab={\overset {\scriptstyle {\leftarrow }}{\beta }}={\overset {\scriptstyle {\leftarrow }}{\gamma }}$, но ${\overset {\scriptstyle {\rightarrow }}{\gamma \,}}=b$ и ${\overset {\scriptstyle {\leftarrow }}{\alpha }}=a$. В случае односторонних контекстов и расширений слова из одного и того же класса эквивалентности образовывали непрерывную цепочку вложенных друг в друга префиксов или суффиксов и могли быть однозначно определены длинами самого короткого и самого длинного слов в классе. В случае же двусторонних расширений однозначно можно сказать только то, что слова из одного и того же класса являются подсловами самого длинного слова из этого класса, а в остальном классы могут иметь достаточно сложную структуру. Общее число таких классов эквивалентности не превосходит $n+1$, из чего следует, что у сжатого суффиксного автомата строки длины $n$ будет не больше $n+1$ состояний. Количество переходов в таком автомате не превосходит $2n-2$.

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

Пусть задан набор слов $T=\{S_{1},S_{2},\dots ,S_{k}\}$. Аналогично автомату, построенному по единственному слову $S$ можно рассмотреть обобщённый суффиксный автомат, который принимает язык слов, являющихся суффиксом хотя бы одного слова из $T$. При этом для числа состояний и переходов данного автомата будут выполняться все те же ограничения, которые были указаны выше, если положить $n=|S_{1}|+|S_{2}|+\dots +|S_{k}|$. Сам алгоритм построения по своей сути похож на алгоритм построения автомата для одной строки, но вместо указателя $last$ на состояние соответствующее слову $\omega$ при переходе к слову $\omega x$ функция add_letter будет принимать указатель на состояние, принимающее слово $\omega _{i}$, подразумевая, что переход происходит от текущего набора слов $\{\omega _{1},\dots ,\omega _{i},\dots ,\omega _{k}\}$ к набору $\{\omega _{1},\dots ,\omega _{i}x,\dots ,\omega _{k}\}$. Помимо основных действий, которые уже заложены в алгоритм нужно будет отдельно разобрать случай когда строка $\omega _{i}x$ уже присутствует в автомате — в таком случае, возможно, придётся расщепить состояние, которое её принимает, аналогично тому, как это происходило при формировании суффиксной ссылки в алгоритме для единичного слова.

Дальнейшим развитием этой идеи стало построение суффиксного автомата для случая когда набор $T$ задан не в явном виде, а префиксным деревом на $Q$ вершинах. Мохри и другие показали, что такой автомат содержит не более $2Q-2$ состояний и может быть построен за линейное от своего размера время. При этом количество переходов в таком автомате может достигать $O(Q|\Sigma |)$ — например, если рассмотреть множество слов $T=\{\sigma _{1},a\sigma _{1},a^{2}\sigma _{1},\dots ,a^{n}\sigma _{1},a^{n}\sigma _{2},\dots ,a^{n}\sigma _{k}\}$ над алфавитом $\Sigma =\{a,\sigma _{1},\dots ,\sigma _{k}\}$, то суммарная длина слов из этого множества будет порядка ${\textstyle O(n^{2}+nk)}$, число вершин в соответствующем префиксном дереве будет равна $O(n+k)$, а в суффиксном автомате будет порядка $O(n+k)$ состояний и $O(nk)$ переходов. Сам алгоритм, предложенный Мохри, во многом повторяет общий алгоритм построения автомата по набору строк, но вместо того, чтобы каждый раз дописывать символы слова из набора от начала до конца, алгоритм обходит префиксное дерево в порядке обхода в ширину и приписывает очередные символы в том порядке, в котором встречает их при обходе, что гарантирует амортизированно линейное время работы алгоритма.

Скользящее окно

В некоторых алгоритмах сжатия, таких как LZ77 и RLE может быть полезным хранить суффиксный автомат или подобную структуру не для всего считанного слова, а только для $k$ последних символов. В первую очередь, такая необходимость всплывает из-за специфики задач сжатия данных, где сжимаемые строки обычно достаточно велики и использование $O(n)$ памяти нежелательно. В 1985 году Джанет Блумер разработала алгоритм, поддерживающий суффиксный автомат на скользящем окне размера $k$ и работающий за $O(nk)$ в худшем случае и $O(n\log k)$ в среднем, в предположении, что символы в сжимаемом слове распределены независимо и равномерно. В той же работе было показано, что оценка $O(nk)$ является неулучшаемой — если рассмотреть слова, полученные конкатенацией нескольких слов вида $(ab)^{m}c(ab)^{m}d$, где $k=6m+2$, то число состояний автомата, который соответствует подсловам длины $k$ чередовалось бы с резкими прыжками порядка $m$ по величине, что делает существование даже теоретического алгоритма, улучшающего оценку в $O(nk)$ для суффиксного автомата невозможным.

Казалось бы, то же самое должно быть верно и для суффиксного дерева, так как вершины суффиксного дерева соответствуют состояниям суффиксного автомата развёрнутой строки. Однако, если в суффиксном дереве не выделять отдельную вершину для каждого суффикса, то таких резких скачков уже не будет и построение амортизированного алгоритма, поддерживающего суффиксное дерево на скользящем окне возможно. Соответствующий алгоритм для суффиксного дерева, поддерживающий добавление нового символа справа и удаление символа слева, был предложен в 1989 году. В связи с этим долгое время оставался открытым вопрос о том, возможно ли поддержание быстрого скользящего окна для сжатого автомата, который объединяет в себе некоторые свойства как обычного суффиксного автомата, так и суффиксного дерева. Отрицательный ответ на этот вопрос был получен в 2009 Мартином Сенфтом и Томашем Двораком, показавшим, что если алфавит состоит из двух и более символов, то амортизированное время, требуемое для сдвига окна на один символ в худшем случае имеет порядок $O(k)$.

Применения

Суффиксный автомат строки $S$ может использоваться для решения таких задач, как:

• Подсчёт количества различных подстрок $S$ за время $O(|S|)$ в режиме онлайн,
• Поиск самой длинной подстроки $S$, которая входит в неё хотя бы два раза, за время $O(|S|)$,
• Поиск наибольшей общей подстроки строк $S$ и $T$ за время $O(|T|)$,
• Подсчёт числа вхождений строки $T$ в $S$ в качестве подстроки за время $O(|T|)$,
• Поиск всех вхождений $T$ в $S$ за время $O(|T|+k)$, где $k$ — количество вхождений.

Здесь стоит считать, что некоторая строка $T$ подаётся на вход, когда автомат уже построен и готов к использованию.

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

Ссылки

• Суффиксный автомат. Построение за O(N) и применения  (неопр.). MAXimal.
• Суффиксный автомат  (неопр.). Викиконспекты ИТМО.