70
правок
Изменения
Нет описания правки
{{Определение
|definition=
Пусть дана строка <tex>s</tex>, <tex>|s| = mn</tex>. Суффиксное дерево (сжатое суффиксное дерево) <tex>T</tex> для строки <tex>s</tex> - ориентированное дерево с корнем, имеющее ровно <tex>mn</tex> листьев, занумерованных от <tex>1</tex> до <tex>mn</tex>. Каждая внутренняя вершина, отличная от корня, имеет не меньше двух детей, а каждая дуга помечена непустой подстрокой строки <tex>s</tex>. Никакие две дуги не могут иметь пометок, начинающихся с одного и того же символа.
}}
Главная особенность суффиксного дерева заключается в том, что для каждого листа <tex>i</tex> конкатенация меток дуг на пути от корня к листу <tex>i</tex> в точности составляет суффикс строки <tex>s</tex>, который начинается в позиции <tex>i</tex>, то есть <tex>s[i..mn]</tex>.
==Существование сжатого суффиксного дерева==
[[Файл:Suffix_tree.jpg|thumb|right|Суффиксный бор для строки <tex>xabxa</tex> с защитным символом]]
Пусть <tex>P</tex> - [[Суффиксный бор|суффиксный бор]] строки <tex>s</tex>. Тогда сжатое суффиксное дерево <tex>T</tex> может быть получено из <tex>P</tex> слиянием каждого пути из неветвящихся вершин в одну дугу.
==Хранение в памяти==
В суффиксном дереве количество разветвлений не более количества листьев, поэтому для его хранения требуется <tex>O(n|\Sigma|)</tex> памяти.
==Источники==
Дэн Гасфилд - Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология - СПб.: Невский Диалект; БХВ-Петербург, 2003. — 654 с: ил.
