Изменения

Перейти к: навигация, поиск

Суффиксный бор

11 байт добавлено, 07:42, 15 марта 2011
Хранение в памяти
==Хранение в памяти==
Пусть <tex>s \in \Sigma^*</tex>. Из третьего свойства следует, что для хранения суффиксного бора в худшем случае потребуется <tex>O(n^2 |\Sigma|)</tex> памяти. Если не хранить массив переходов по символам для вершин, где такой переход единственный, получаем можно получить оценку <tex>O(n^2 + n|\Sigma|)</tex>. Улучшением суффиксного бора, расходующим всего <tex>O( n|\Sigma|)</tex> памяти, является [[Сжатое суффиксное дерево|сжатый суффиксный бор]].
322
правки

Навигация