Изменения
Нет описания правки
==Хранение в памяти==
В суффиксном дереве количество разветвлений не более количества листьев, поэтому для его хранения требуется <tex>O(n|\Sigma|)</tex> памяти.
==Использование==
Суффиксное дерево позволяет за линейное время найти:
* Количество различных подстрок данной строки
* Наибольшую общую подстроку двух строк
* Все вхождения заданного образца в строку
* [[Суффиксный массив| Суффиксный массив]] и массив <tex>lcp</tex> (longest common prefix)
==Источники==
Дэн Гасфилд - Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология - СПб.: Невский Диалект; БХВ-Петербург, 2003. — 654 с: ил.
