Изменения

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

Будем обозначать длину самой длинной строки, которая принимается состоянием <tex>q</tex> как <tex>\mathrm{len_q}</tex>. Длина самой короткой строки из <tex>q</tex> в таком случае будет равна <tex>\mathrm{len(link_q) } + 1</tex>.

Изначально автомат состоит из одного состояния, для которого <tex>\mathrm{len(0) } = 0</tex>, а <tex>\mathrm{link_0 } = -1</tex>.<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>\mathrm{len(p) } + 1 = \mathrm{len(q)}</tex>, то <tex>\mathrm{link(q) } = \mathrm{cur}</tex>.<br># В противном случае, создадим новое состояние <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>\mathrm{last } = \mathrm{cur}</tex>.

# Изначально автомат состоит из одного начального состояния. <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>\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>\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>\mathrm{last } = 3, \mathrm{len(3) } = 3</tex>.<br><br>[[Файл:Suffix_automaton_s4.png|x180px|thumb|center|Шаг 4.]]<br>

# Рассмотрим состояние <tex>2</tex>, куда существует переход. Имеем <tex>\mathrm{len(0) } + 1 \neq \mathrm{len(2)}</tex>.

## Копируем в него все суффиксные ссылки и переходы из <tex>2</tex> и присвоим <tex>\mathrm{len(5) } = \mathrm{len(0) } + 1 = 1</tex>.

* Суффиксные ссылки хранятся в массиве <tex>\mathrm{link}</tex>, * Длины строк хранятся в массиве <tex>\mathrm{len}</tex>,* Функция <tex>\mathrm{newState}</tex> создаёт новое состояние и возвращает его номер,* Функция <tex>\mathrm{clone}</tex> копирует состояние и возвращает номер нового состояния.

Пусть текущее состояние {{---}} <tex>\mathrm{cur}</tex>, изначально равно <tex>0</tex> (начальному состоянию).<br>Будем по очереди обрабатывать символы строки <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>.

В процессе построения для каждого состояния <tex>q</tex> будем хранить значение <tex>\mathrm{first(q)}</tex> {{---}} позицию окончания первого вхождения строки.Поддерживать позицию <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>\mathrm{first(p') } - |p| + 1</tex>.