188
правок
Изменения
Нет описания правки
}}
Будем обозначать длину самой длинной строки, которая принимается состоянием <tex>q</tex> как <tex>len_q</tex>. Длина самой короткой строки из <tex>q</tex> в таком случае будет равна <tex>len(link_q) + 1</tex>.
Суффиксный автомат может быть построен за линейное время (при константном размере алфавита) online-алгоритмом. Будем добавлять символы строки <tex>s</tex> по одному, перестраивая при этом автомат.
Изначально автомат состоит из одного состояния, для которого <tex>len(0) = 0</tex>, а <tex>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>
Построим суффиксный автомат для строки <tex>s</tex>.<br>
Каждой подстроке в суффиксном автомате соответствует путь, тогда ответ на задачу {{---}} количество различных путей из начальной вершины. Так как суфавтомат представляет собой ациклический граф, мы можем найти [[Задача_о_числе_путей_в_ациклическом_графе|количество путей в графе методом динамического программирования]].
==Сравнение с другими суффиксными структурами==
Пусть <tex>s</tex> {{---}} строка, для которой строим соответствующую структуру, <tex>n = |s|</tex>, <tex>\Sigma</tex> {{---}} [[Основные_определения:_алфавит,_слово,_язык,_конкатенация,_свободный_моноид_слов;_операции_над_языками|алфавит]].
{| class="wikitable"
|-
|
| align="center" | '''Время работы'''
| align="center" | '''Память'''
|-
| align="center" | [[Суффиксный бор]]
| align="center" | <tex>O(n ^ 2)</tex>
| align="center" | <tex>O(n^2 + n |\Sigma|)</tex>
|-
| align="center" | [[Сжатое суффиксное дерево]]
| align="center" | <tex>O(n \log{|\Sigma|})</tex>
| align="center" | <tex>O(n |\Sigma|)</tex>
|-
| align="center" | [[Суффиксный массив]]
| align="center" | <tex>O((n + |\Sigma|) \log{n})</tex>
| align="center" | <tex>O(n + |\Sigma|)</tex>
|-
| align="center" | Суффиксный автомат
| align="center" | <tex>O(n \log{|\Sigma|})</tex>
| align="center" | <tex>O(n)</tex>
|}
==Источники информации==
