188
правок
Изменения
Нет описания правки
==Построение==
===Алгоритм===
{{Определение
|definition =
# В противном случае, создадим новое состояние <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>last = cur</tex>.
===Пример построения===
Рассмотрим построение суффиксного автомата для строки <tex>abcb</tex>. Серыми стрелками показаны суффиксные ссылки.
# Изначально автомат состоит из одного начального состояния. <tex>last = 0, 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>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>c</tex> и обновим автомат. <tex>last = 3, 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>2</tex>, куда существует переход. Имеем <tex>len(0) + 1 \neq len(2)</tex>.
## Создаем новое состояние <tex>5</tex>.
## Копируем в него все суффиксные ссылки и переходы из <tex>2</tex> и присвоим <tex>len(5) = 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>abcb</tex> и пройдём по суффиксным ссылкам, помечая все посещенные состояния терминальными.<br><br>[[Файл:Suffix_automaton_s7.png|x180px|thumb|center|Шаг 7.]]
==Реализация==
