Суффиксный автомат — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 48: Строка 48:
 
{{Определение
 
{{Определение
 
|definition =  
 
|definition =  
Пусть длина самой короткой строки, которая принимается состоянием <tex>q</tex> равно <tex>k</tex>, тогда '''суффиксная ссылка''' <tex>link_q</tex> будет вести из этого состояния в состояние, которое принимает эту же строку без первого символа.
+
Пусть длина самой короткой строки, которая принимается состоянием <tex>q</tex> равно <tex>k</tex>, тогда '''суффиксная ссылка''' <tex>\mathrm{link_q}</tex> будет вести из этого состояния в состояние, которое принимает эту же строку без первого символа.
 
}}
 
}}
Будем обозначать длину самой длинной строки, которая принимается состоянием <tex>q</tex> как <tex>len_q</tex>. Длина самой короткой строки из <tex>q</tex> в таком случае будет равна <tex>len(link_q) + 1</tex>.  
+
Будем обозначать длину самой длинной строки, которая принимается состоянием <tex>q</tex> как <tex>\mathrm{len_q}</tex>. Длина самой короткой строки из <tex>q</tex> в таком случае будет равна <tex>\mathrm{len(link_q)} + 1</tex>.  
 
Суффиксный автомат может быть построен за линейное время (при константном размере алфавита) online-алгоритмом. Будем добавлять символы строки <tex>s</tex> по одному, перестраивая при этом автомат.  
 
Суффиксный автомат может быть построен за линейное время (при константном размере алфавита) online-алгоритмом. Будем добавлять символы строки <tex>s</tex> по одному, перестраивая при этом автомат.  
Изначально автомат состоит из одного состояния, для которого <tex>len(0) = 0</tex>, а <tex>link_0 = -1</tex>.
+
Изначально автомат состоит из одного состояния, для которого <tex>\mathrm{len(0)} = 0</tex>, а <tex>\mathrm{link_0} = -1</tex>.
<br>Обозначим состояние <tex>last</tex>, соответствующее текущей строке до добавления символа <tex>c</tex> (изначально <tex>last = 0</tex>). <br>Создадим новое состояние <tex>cur</tex>, <tex>len(cur) = len(last) + 1</tex>. <br>Рассмотрим все переходы из <tex>last</tex> по текущему символу <tex>c</tex>. Если перехода нет, то добавляем переход в <tex>cur</tex>, переходим по суффиксной ссылке и повторяем процедуру снова. Если переход существует, то остановимся и обозначим текущее состояние за <tex>p</tex>. Если перехода не нашлось и по суффиксным ссылкам мы дошли до фиктивного состояния (на которое указывает <tex>link_0</tex>), то <tex>link_{cur} = 0</tex>.<br>
+
<br>Обозначим состояние <tex>\mathrm{last}</tex>, соответствующее текущей строке до добавления символа <tex>c</tex> (изначально <tex>\mathrm{last} = 0</tex>). <br>Создадим новое состояние <tex>\mathrm{cur}</tex>, <tex>\mathrm{len(cur)} = \mathrm{len(last)} + 1</tex>. <br>Рассмотрим все переходы из <tex>\mathrm{last}</tex> по текущему символу <tex>c</tex>. Если перехода нет, то добавляем переход в <tex>\mathrm{cur}</tex>, переходим по суффиксной ссылке и повторяем процедуру снова. Если переход существует, то остановимся и обозначим текущее состояние за <tex>p</tex>. Если перехода не нашлось и по суффиксным ссылкам мы дошли до фиктивного состояния (на которое указывает <tex>\mathrm{link_0}</tex>), то <tex>\mathrm{link_{cur}} = 0</tex>.<br>
 
Допустим, что мы остановились в состоянии <tex>p</tex>, из которого существует переход с символом <tex>c</tex>. Обозначим состояние, куда ведёт переход, через <tex>q</tex>. Рассмотрим два случая:<br>
 
Допустим, что мы остановились в состоянии <tex>p</tex>, из которого существует переход с символом <tex>c</tex>. Обозначим состояние, куда ведёт переход, через <tex>q</tex>. Рассмотрим два случая:<br>
# Если <tex>len(p) + 1 = len(q)</tex>, то <tex>link(q) = cur</tex>.<br>
+
# Если <tex>\mathrm{len(p)} + 1 = \mathrm{len(q)}</tex>, то <tex>\mathrm{link(q)} = \mathrm{cur}</tex>.<br>
# В противном случае, создадим новое состояние <tex>new</tex>, скопируем в него <tex>q</tex> вместе с суффиксными ссылками и переходами. <tex>len(new)</tex> присвоим значение <tex>len(p) + 1</tex>. Перенаправим суффиксную ссылку из <tex>q</tex> в <tex>new</tex> и добавим ссылку из <tex>cur</tex> в <tex>new</tex>. Пройдём по всем суффиксным ссылкам из состояния <tex>p</tex> и все переходы в состояние <tex>q</tex> по символу <tex>c</tex> перенаправим в <tex>new</tex>.
+
# В противном случае, создадим новое состояние <tex>\mathrm{new}</tex>, скопируем в него <tex>q</tex> вместе с суффиксными ссылками и переходами. <tex>\mathrm{len(new)}</tex> присвоим значение <tex>\mathrm{len(p)} + 1</tex>. Перенаправим суффиксную ссылку из <tex>q</tex> в <tex>\mathrm{new}</tex> и добавим ссылку из <tex>\mathrm{cur}</tex> в <tex>\mathrm{new}</tex>. Пройдём по всем суффиксным ссылкам из состояния <tex>p</tex> и все переходы в состояние <tex>q</tex> по символу <tex>c</tex> перенаправим в <tex>\mathrm{new}</tex>.
Обновим значение <tex>last = cur</tex>.
+
Обновим значение <tex>\mathrm{last} = \mathrm{cur}</tex>.
 
===Пример построения===
 
===Пример построения===
 
Рассмотрим построение суффиксного автомата для строки <tex>abcb</tex>. Серыми стрелками показаны суффиксные ссылки.
 
Рассмотрим построение суффиксного автомата для строки <tex>abcb</tex>. Серыми стрелками показаны суффиксные ссылки.
# Изначально автомат состоит из одного начального состояния. <tex>last = 0, len(0) = 0</tex>.<br><br>[[Файл:Suffix_automaton_s1.png|x180px|thumb|center|Шаг 1.]]<br>
+
# Изначально автомат состоит из одного начального состояния. <tex>\mathrm{last} = 0, \mathrm{len(0)} = 0</tex>.<br><br>[[Файл:Suffix_automaton_s1.png|x180px|thumb|center|Шаг 1.]]<br>
# Добавляем символ <tex>a</tex>. Создаем состояние <tex>1</tex>. Переходов из начального состояния по символу <tex>a</tex> нет, перейти по суффиксным ссылкам некуда, значит добавим суффиксную ссылку <tex>link_{1} = 0</tex>. <tex>last = 1, len(1) = 1</tex>.<br><br>[[Файл:Suffix_automaton_s2.png|x180px|thumb|center|Шаг 2.]]<br>
+
# Добавляем символ <tex>a</tex>. Создаем состояние <tex>1</tex>. Переходов из начального состояния по символу <tex>a</tex> нет, перейти по суффиксным ссылкам некуда, значит добавим суффиксную ссылку <tex>\mathrm{link_{1}} = 0</tex>. <tex>\mathrm{last} = 1, \mathrm{len(1)} = 1</tex>.<br><br>[[Файл:Suffix_automaton_s2.png|x180px|thumb|center|Шаг 2.]]<br>
# Добавляем символ <tex>b</tex>. Создаем состояние <tex>2</tex>. Добавим переход из <tex>1</tex>, откатимся по суффиксной ссылке и добавим переход из <tex>0</tex>. Добавим суффиксную ссылку <tex>link_{2} = 0</tex>. <tex>last = 2, len(2) = 2</tex>.<br><br>[[Файл:Suffix_automaton_s3.png|x180px|thumb|center|Шаг 3.]]<br>
+
# Добавляем символ <tex>b</tex>. Создаем состояние <tex>2</tex>. Добавим переход из <tex>1</tex>, откатимся по суффиксной ссылке и добавим переход из <tex>0</tex>. Добавим суффиксную ссылку <tex>\mathrm{link_{2}} = 0</tex>. <tex>\mathrm{last} = 2, \mathrm{len(2)} = 2</tex>.<br><br>[[Файл:Suffix_automaton_s3.png|x180px|thumb|center|Шаг 3.]]<br>
# Аналогично добавим символ <tex>c</tex> и обновим автомат. <tex>last = 3, len(3) = 3</tex>.<br><br>[[Файл:Suffix_automaton_s4.png|x180px|thumb|center|Шаг 4.]]<br>
+
# Аналогично добавим символ <tex>c</tex> и обновим автомат. <tex>\mathrm{last} = 3, \mathrm{len(3)} = 3</tex>.<br><br>[[Файл:Suffix_automaton_s4.png|x180px|thumb|center|Шаг 4.]]<br>
 
# Добавляем символ <tex>b</tex>. Добавим переход из <tex>3</tex> и перейдем по суффиксной ссылке в начальное состояние. Из состояния <tex>0</tex> существует переход по символу <tex>b</tex>.<br><br>[[Файл:Suffix_automaton_s5.png|x180px|thumb|center|Шаг 5.]]<br>
 
# Добавляем символ <tex>b</tex>. Добавим переход из <tex>3</tex> и перейдем по суффиксной ссылке в начальное состояние. Из состояния <tex>0</tex> существует переход по символу <tex>b</tex>.<br><br>[[Файл:Suffix_automaton_s5.png|x180px|thumb|center|Шаг 5.]]<br>
# Рассмотрим состояние <tex>2</tex>, куда существует переход. Имеем <tex>len(0) + 1 \neq len(2)</tex>.
+
# Рассмотрим состояние <tex>2</tex>, куда существует переход. Имеем <tex>\mathrm{len(0)} + 1 \neq \mathrm{len(2)}</tex>.
 
## Создаем новое состояние <tex>5</tex>.
 
## Создаем новое состояние <tex>5</tex>.
## Копируем в него все суффиксные ссылки и переходы из <tex>2</tex> и присвоим <tex>len(5) = len(0) + 1 = 1</tex>.
+
## Копируем в него все суффиксные ссылки и переходы из <tex>2</tex> и присвоим <tex>\mathrm{len(5)} = \mathrm{len(0)} + 1 = 1</tex>.
 
## Перенаправим суффиксную ссылку из <tex>2</tex> в <tex>5</tex> и добавим ссылку из <tex>4</tex> в <tex>5</tex>. Перенаправим переход <tex>0 \rightarrow 2</tex> в состояние <tex>5</tex>.<br><br>[[Файл:Suffix_automaton_s6.png|x180px|thumb|center|Шаг 6.]]<br>
 
## Перенаправим суффиксную ссылку из <tex>2</tex> в <tex>5</tex> и добавим ссылку из <tex>4</tex> в <tex>5</tex>. Перенаправим переход <tex>0 \rightarrow 2</tex> в состояние <tex>5</tex>.<br><br>[[Файл:Suffix_automaton_s6.png|x180px|thumb|center|Шаг 6.]]<br>
 
# Построение автомата завершено. Чтобы пометить терминальные вершины, найдём состояние, которое принимает строку <tex>abcb</tex> и пройдём по суффиксным ссылкам, помечая все посещенные состояния терминальными.<br><br>[[Файл:Suffix_automaton_s7.png|x180px|thumb|center|Шаг 7.]]
 
# Построение автомата завершено. Чтобы пометить терминальные вершины, найдём состояние, которое принимает строку <tex>abcb</tex> и пройдём по суффиксным ссылкам, помечая все посещенные состояния терминальными.<br><br>[[Файл:Suffix_automaton_s7.png|x180px|thumb|center|Шаг 7.]]
Строка 73: Строка 73:
 
==Реализация==
 
==Реализация==
 
* Переходы хранятся в массиве отображений (ключ {{---}} символ, значение {{---}} номер состояния) <tex>edges</tex>,
 
* Переходы хранятся в массиве отображений (ключ {{---}} символ, значение {{---}} номер состояния) <tex>edges</tex>,
* Суффиксные ссылки хранятся в массиве <tex>link</tex>,  
+
* Суффиксные ссылки хранятся в массиве <tex>\mathrm{link}</tex>,  
* Длины строк хранятся в массиве <tex>len</tex>,
+
* Длины строк хранятся в массиве <tex>\mathrm{len}</tex>,
* Функция <tex>newState</tex> создаёт новое состояние и возвращает его номер,
+
* Функция <tex>\mathrm{newState}</tex> создаёт новое состояние и возвращает его номер,
* Функция <tex>clone</tex> копирует состояние и возвращает номер нового состояния.
+
* Функция <tex>\mathrm{clone}</tex> копирует состояние и возвращает номер нового состояния.
  
 
  '''func''' addChar(c)''':'''
 
  '''func''' addChar(c)''':'''
Строка 106: Строка 106:
 
}}
 
}}
 
Построим суффиксный автомат для строки <tex>s</tex>.<br>
 
Построим суффиксный автомат для строки <tex>s</tex>.<br>
Пусть текущее состояние {{---}} <tex>cur</tex>, изначально равно <tex>0</tex> (начальному состоянию).<br>
+
Пусть текущее состояние {{---}} <tex>\mathrm{cur}</tex>, изначально равно <tex>0</tex> (начальному состоянию).<br>
Будем по очереди обрабатывать символы строки <tex>p</tex>. Если из состояния <tex>cur</tex> есть переход в по текущему символу, но перейдем в новое состояние и повторим процедуру. Если перехода не существует, то <tex>p</tex> не является подстрокой <tex>s</tex>. Если успешно обработали все символы <tex>p</tex>, то она является подстрокой <tex>s</tex>.<br>Асимптотика {{---}} построение суфавтомата за <tex>O(|s|)</tex>, проверка за <tex>O(|p|)</tex>.
+
Будем по очереди обрабатывать символы строки <tex>p</tex>. Если из состояния <tex>\mathrm{cur}</tex> есть переход в по текущему символу, но перейдем в новое состояние и повторим процедуру. Если перехода не существует, то <tex>p</tex> не является подстрокой <tex>s</tex>. Если успешно обработали все символы <tex>p</tex>, то она является подстрокой <tex>s</tex>.<br>Асимптотика {{---}} построение суфавтомата за <tex>O(|s|)</tex>, проверка за <tex>O(|p|)</tex>.
  
 
===Позиция первого вхождения строки===
 
===Позиция первого вхождения строки===
Строка 115: Строка 115:
 
}}
 
}}
 
Построим суффиксный автомат для строки <tex>s</tex>.<br>
 
Построим суффиксный автомат для строки <tex>s</tex>.<br>
В процессе построения для каждого состояния <tex>q</tex> будем хранить значение <tex>first(q)</tex> {{---}} позицию окончания первого вхождения строки.
+
В процессе построения для каждого состояния <tex>q</tex> будем хранить значение <tex>\mathrm{first(q)}</tex> {{---}} позицию окончания первого вхождения строки.
Поддерживать позицию <tex>first</tex> можно следующим образом: при добавлении нового состояния <tex>first(cur) = len(cur) - 1</tex>, а при клонировании вершины <tex>first(new) = first(q)</tex>.<br>
+
Поддерживать позицию <tex>\mathrm{first}</tex> можно следующим образом: при добавлении нового состояния <tex>\mathrm{first(cur)} = \mathrm{len(cur)} - 1</tex>, а при клонировании вершины <tex>\mathrm{first(new)} = \mathrm{first(q)}</tex>.<br>
Для поиска вхождения обойдём автомат, как в предыдущей задаче. Пусть состояние <tex>p'</tex> в автомате соответствует строке <tex>p</tex>. Тогда ответ на задачу <tex>first(p') - |p| + 1</tex>.
+
Для поиска вхождения обойдём автомат, как в предыдущей задаче. Пусть состояние <tex>p'</tex> в автомате соответствует строке <tex>p</tex>. Тогда ответ на задачу <tex>\mathrm{first(p')} - |p| + 1</tex>.
 
<br>Асимптотика {{---}} построение суфавтомата за <tex>O(|s|)</tex>, проверка за <tex>O(|p|)</tex>.
 
<br>Асимптотика {{---}} построение суфавтомата за <tex>O(|s|)</tex>, проверка за <tex>O(|p|)</tex>.
 
===Количество различных подстрок===
 
===Количество различных подстрок===

Версия 19:24, 26 марта 2016

Определение:
Суффиксный автомат (англ. suffix automaton, directed acyclic word graph) — минимальный ДКА, который принимает все суффиксы строки и только их.


Описание

Детерминированным конечным автоматом называется пятёрка ([math]S, s, \Sigma, \delta, T)[/math]), где

  • [math]S[/math] — множество состояний,
  • [math]s \in S[/math] — начальное состояние,
  • [math]\Sigma[/math] — конечный алфавит,
  • [math]\delta : S \times \Sigma \to S[/math] — функция переходов,
  • [math]T \subset S[/math] — множество терминальных состояний.

Суффиксный автомат [math]A[/math] для строки [math]s[/math] представляет собой ациклический ориентированный граф, с начальной вершиной и множеством терминальных вершин, рёбра которого помечены символами [math]s[/math].

Пример суффиксного автомата для строки [math]abbab[/math].


Определение:
Состояние [math]q[/math] принимает строку [math]s[/math], если существует путь из начального состояния в [math]q[/math], такой, что если последовательно выписать буквы на рёбрах на пути, получим строку [math]s[/math].


Определение:
Автомат принимает строку [math]s[/math], если её принимает хотя бы одно из финальных состояний.


Так как автомат детерминированный, то каждому пути соответствует строка.

Если две строки [math]a[/math] и [math]b[/math] принимаются одним состоянием [math]q[/math] произвольного автомата, то для любой строки [math]x[/math] строки [math]ax[/math] и [math]bx[/math] принимаются или не принимаются автоматом одновременно. Действительно, независимо от того, как мы пришли в состояние [math]q[/math], если мы пройдём из него по пути, соответствующему строке [math]x[/math], мы сможем точно сказать, в какое состояние мы попадём (в частности, будет ли оно финальным). Значит, любому состоянию [math]q[/math] соответствует множество строк [math]X_q[/math], которые переводят его в одно из конечных состояний.

Определение:
Множество [math]X_q[/math] называют правым контекстом состояния.


Правый контекст определен не только для состояния, но и для строк, которые оно принимает — правый контекст строк совпадает с правым контекстом состояния.

Утверждение:
Состояний в автомате не меньше, чем различных правых контекстов у подстрок строки, для которой он построен, причём в минимальном автомате достигается нижняя оценка.
[math]\triangleright[/math]
Допустим, что в автомате есть два состояния [math]q_1[/math] и [math]q_2[/math] такие что [math]X_{q_1} = X_{q_2}[/math]. Мы можем удалить состояние [math]q_2[/math] и перевести переходы, ведущие в него в состояние [math]q_1[/math]. Множество принимаемых строк от этого не изменится, следовательно, мы можем продолжать, пока количество состояний не будет равно числу попарно различных правых контекстов.
[math]\triangleleft[/math]

Таким образом, ДКА является минимальным тогда и только тогда, когда правые контексты всех его состояний попарно различны. В случае суффиксного автомата правый контекст [math]X_a[/math] строки [math]a[/math] взаимнооднозначно соответствует множеству правых позиций вхождений строки [math]a[/math] в строку [math]s[/math]. Таким образом, каждое состояние автомата принимает строки с одинаковым множеством правых позиций их вхождений и обратно, все строки с таким множеством позиций принимается этим состоянием.

Построение

Алгоритм

Определение:
Пусть длина самой короткой строки, которая принимается состоянием [math]q[/math] равно [math]k[/math], тогда суффиксная ссылка [math]\mathrm{link_q}[/math] будет вести из этого состояния в состояние, которое принимает эту же строку без первого символа.

Будем обозначать длину самой длинной строки, которая принимается состоянием [math]q[/math] как [math]\mathrm{len_q}[/math]. Длина самой короткой строки из [math]q[/math] в таком случае будет равна [math]\mathrm{len(link_q)} + 1[/math]. Суффиксный автомат может быть построен за линейное время (при константном размере алфавита) online-алгоритмом. Будем добавлять символы строки [math]s[/math] по одному, перестраивая при этом автомат. Изначально автомат состоит из одного состояния, для которого [math]\mathrm{len(0)} = 0[/math], а [math]\mathrm{link_0} = -1[/math].
Обозначим состояние [math]\mathrm{last}[/math], соответствующее текущей строке до добавления символа [math]c[/math] (изначально [math]\mathrm{last} = 0[/math]).
Создадим новое состояние [math]\mathrm{cur}[/math], [math]\mathrm{len(cur)} = \mathrm{len(last)} + 1[/math].
Рассмотрим все переходы из [math]\mathrm{last}[/math] по текущему символу [math]c[/math]. Если перехода нет, то добавляем переход в [math]\mathrm{cur}[/math], переходим по суффиксной ссылке и повторяем процедуру снова. Если переход существует, то остановимся и обозначим текущее состояние за [math]p[/math]. Если перехода не нашлось и по суффиксным ссылкам мы дошли до фиктивного состояния (на которое указывает [math]\mathrm{link_0}[/math]), то [math]\mathrm{link_{cur}} = 0[/math].
Допустим, что мы остановились в состоянии [math]p[/math], из которого существует переход с символом [math]c[/math]. Обозначим состояние, куда ведёт переход, через [math]q[/math]. Рассмотрим два случая:

  1. Если [math]\mathrm{len(p)} + 1 = \mathrm{len(q)}[/math], то [math]\mathrm{link(q)} = \mathrm{cur}[/math].
  2. В противном случае, создадим новое состояние [math]\mathrm{new}[/math], скопируем в него [math]q[/math] вместе с суффиксными ссылками и переходами. [math]\mathrm{len(new)}[/math] присвоим значение [math]\mathrm{len(p)} + 1[/math]. Перенаправим суффиксную ссылку из [math]q[/math] в [math]\mathrm{new}[/math] и добавим ссылку из [math]\mathrm{cur}[/math] в [math]\mathrm{new}[/math]. Пройдём по всем суффиксным ссылкам из состояния [math]p[/math] и все переходы в состояние [math]q[/math] по символу [math]c[/math] перенаправим в [math]\mathrm{new}[/math].

Обновим значение [math]\mathrm{last} = \mathrm{cur}[/math].

Пример построения

Рассмотрим построение суффиксного автомата для строки [math]abcb[/math]. Серыми стрелками показаны суффиксные ссылки.

  1. Изначально автомат состоит из одного начального состояния. [math]\mathrm{last} = 0, \mathrm{len(0)} = 0[/math].

    Шаг 1.

  2. Добавляем символ [math]a[/math]. Создаем состояние [math]1[/math]. Переходов из начального состояния по символу [math]a[/math] нет, перейти по суффиксным ссылкам некуда, значит добавим суффиксную ссылку [math]\mathrm{link_{1}} = 0[/math]. [math]\mathrm{last} = 1, \mathrm{len(1)} = 1[/math].

    Шаг 2.

  3. Добавляем символ [math]b[/math]. Создаем состояние [math]2[/math]. Добавим переход из [math]1[/math], откатимся по суффиксной ссылке и добавим переход из [math]0[/math]. Добавим суффиксную ссылку [math]\mathrm{link_{2}} = 0[/math]. [math]\mathrm{last} = 2, \mathrm{len(2)} = 2[/math].

    Шаг 3.

  4. Аналогично добавим символ [math]c[/math] и обновим автомат. [math]\mathrm{last} = 3, \mathrm{len(3)} = 3[/math].

    Шаг 4.

  5. Добавляем символ [math]b[/math]. Добавим переход из [math]3[/math] и перейдем по суффиксной ссылке в начальное состояние. Из состояния [math]0[/math] существует переход по символу [math]b[/math].

    Шаг 5.

  6. Рассмотрим состояние [math]2[/math], куда существует переход. Имеем [math]\mathrm{len(0)} + 1 \neq \mathrm{len(2)}[/math].
    1. Создаем новое состояние [math]5[/math].
    2. Копируем в него все суффиксные ссылки и переходы из [math]2[/math] и присвоим [math]\mathrm{len(5)} = \mathrm{len(0)} + 1 = 1[/math].
    3. Перенаправим суффиксную ссылку из [math]2[/math] в [math]5[/math] и добавим ссылку из [math]4[/math] в [math]5[/math]. Перенаправим переход [math]0 \rightarrow 2[/math] в состояние [math]5[/math].

      Шаг 6.

  7. Построение автомата завершено. Чтобы пометить терминальные вершины, найдём состояние, которое принимает строку [math]abcb[/math] и пройдём по суффиксным ссылкам, помечая все посещенные состояния терминальными.

    Шаг 7.

Реализация

  • Переходы хранятся в массиве отображений (ключ — символ, значение — номер состояния) [math]edges[/math],
  • Суффиксные ссылки хранятся в массиве [math]\mathrm{link}[/math],
  • Длины строк хранятся в массиве [math]\mathrm{len}[/math],
  • Функция [math]\mathrm{newState}[/math] создаёт новое состояние и возвращает его номер,
  • Функция [math]\mathrm{clone}[/math] копирует состояние и возвращает номер нового состояния.
func addChar(c):
    cur = newState()                                       // создаём новое состояние и возвращаем его номер 

    p = last
    while p >= 0 and edges[p].find(c) == null:
        edges[p][c] = cur
        p = link[p]

    if p != -1:
        q = edges[p][c]
        if len[p] + 1 == len[q]:
            link[cur] = q
        else:
            new = clone(q)                                // скопируем состояние [math]q[/math]
            len[new] = len[p] + 1
            link[q] = link[cur] = new
            while p >= 0 and edges[p][c] == q:
                edges[p][c] = new
                p = link[p]
    last = cur

Применение

Проверка вхождения строки

Задача:
Даны строки [math]s[/math] и [math]p[/math]. Требуется проверить, является ли строка [math]p[/math] подстрокой [math]s[/math].

Построим суффиксный автомат для строки [math]s[/math].
Пусть текущее состояние — [math]\mathrm{cur}[/math], изначально равно [math]0[/math] (начальному состоянию).
Будем по очереди обрабатывать символы строки [math]p[/math]. Если из состояния [math]\mathrm{cur}[/math] есть переход в по текущему символу, но перейдем в новое состояние и повторим процедуру. Если перехода не существует, то [math]p[/math] не является подстрокой [math]s[/math]. Если успешно обработали все символы [math]p[/math], то она является подстрокой [math]s[/math].
Асимптотика — построение суфавтомата за [math]O(|s|)[/math], проверка за [math]O(|p|)[/math].

Позиция первого вхождения строки

Задача:
Даны строки [math]s[/math] и [math]p[/math]. Требуется найти позицию первого вхождения строки [math]p[/math] в [math]s[/math].

Построим суффиксный автомат для строки [math]s[/math].
В процессе построения для каждого состояния [math]q[/math] будем хранить значение [math]\mathrm{first(q)}[/math] — позицию окончания первого вхождения строки. Поддерживать позицию [math]\mathrm{first}[/math] можно следующим образом: при добавлении нового состояния [math]\mathrm{first(cur)} = \mathrm{len(cur)} - 1[/math], а при клонировании вершины [math]\mathrm{first(new)} = \mathrm{first(q)}[/math].
Для поиска вхождения обойдём автомат, как в предыдущей задаче. Пусть состояние [math]p'[/math] в автомате соответствует строке [math]p[/math]. Тогда ответ на задачу [math]\mathrm{first(p')} - |p| + 1[/math].
Асимптотика — построение суфавтомата за [math]O(|s|)[/math], проверка за [math]O(|p|)[/math].

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

Задача:
Дана строка [math]s[/math]. Найти количество различных подстрок строки [math]s[/math].

Построим суффиксный автомат для строки [math]s[/math].
Каждой подстроке в суффиксном автомате соответствует путь, тогда ответ на задачу — количество различных путей из начальной вершины. Так как суфавтомат представляет собой ациклический граф, мы можем найти количество путей в графе методом динамического программирования.

Сравнение с другими суффиксными структурами

Пусть [math]s[/math] — строка, для которой строим соответствующую структуру, [math]n = |s|[/math], [math]\Sigma[/math]алфавит.

Время работы Память
Суффиксный бор [math]O(n ^ 2)[/math] [math]O(n^2 + n |\Sigma|)[/math]
Сжатое суффиксное дерево [math]O(n \log{|\Sigma|})[/math] [math]O(n |\Sigma|)[/math]
Суффиксный массив [math]O((n + |\Sigma|) \log{n})[/math] [math]O(n + |\Sigma|)[/math]
Суффиксный автомат [math]O(n \log{|\Sigma|})[/math] [math]O(n)[/math]

Источники информации