Изменения

{{Определение|definition=Пусть дана строка <tex>s</tex>, <tex>|s| = n</tex>. '''Суффиксное дерево ''' (сжатое суффиксное дерево) <tex>T</tex> для строки <tex>s</tex> (где <tex>|s| = n</tex>) {{-- -}} ориентированное дерево с корнем, имеющее ровно <tex>n</tex> листьев, занумерованных от <tex>1</tex> до <tex>n</tex>. Каждая внутренняя вершина, отличная от корня, имеет не меньше двух детей, а каждая дуга помечена непустой подстрокой строки <tex>s</tex>. Никакие две дуги, выходящие из одной и той же вершины, не могут иметь пометок, начинающихся с одного и того же символа. Суффиксное дерево содержит все суффиксы строки <tex>s</tex>: для каждого листа <tex>i</tex> конкатенация меток дуг на пути от корня к листу <tex>i</tex> в точности составляет суффикс, который начинается в позиции <tex>i</tex>, то есть <tex>s[i..n]</tex>.}}

Пусть <tex>P</tex> {{- --}} [[Суффиксный бор|суффиксный бор]] строки <tex>s</tex>. Тогда сжатое суффиксное дерево <tex>T</tex> может быть получено из <tex>P</tex> слиянием каждого пути из неветвящихся вершин в одну дугу.

''Дэн Гасфилд - '' — '''Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология - ''' — СПб.: Невский Диалект; БХВ-Петербург, 2003. — 654 с: ил.