Изменения

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