Изменения

Пусть <tex>s \in \Sigma^*</tex>, <tex>\lvert s\rvert = n</tex>. Из третьего свойства следует, что для хранения суффиксного бора в худшем случае потребуется <tex>O(n^2 |\Sigma|)</tex> памяти. При этом таблица для приведенной выше реализации выглядит так:{| border="1" cellpadding="3" cellspacing="0" style="text-align:center" width=20%!style="background:#f2f2f2"|№!style="background:#f2f2f2"|a!style="background:#f2f2f2"|b!style="background:#f2f2f2"|c|-|style="background:#f9f9f9"|0|style="background:#f9f9f9"|1|style="background:#f9f9f9"|5|style="background:#f9f9f9"|9|-|style="background:#f9f9f9"|1|style="background:#f9f9f9"|-1|style="background:#f9f9f9"|2|style="background:#f9f9f9"|-1|-|style="background:#f9f9f9"|2|style="background:#f9f9f9"|-1|style="background:#f9f9f9"|3|style="background:#f9f9f9"|-1|-|style="background:#f9f9f9"|3|style="background:#f9f9f9"|-1|style="background:#f9f9f9"|-1|style="background:#f9f9f9"|4|-|style="background:#f9f9f9"|4|style="background:#f9f9f9"|-1|style="background:#f9f9f9"|-1|style="background:#f9f9f9"|-1|-|style="background:#f9f9f9"|5|style="background:#f9f9f9"|-1|style="background:#f9f9f9"|6|style="background:#f9f9f9"|8|-|style="background:#f9f9f9"|6|style="background:#f9f9f9"|-1|style="background:#f9f9f9"|-1|style="background:#f9f9f9"|7|-|style="background:#f9f9f9"|7|style="background:#f9f9f9"|-1|style="background:#f9f9f9"|-1|style="background:#f9f9f9"|-1|-|}Если не хранить массив переходов по символам для вершин, где такой переход единственный, то можно получить оценку <tex>O(n^2 + n|\Sigma|)</tex>. Улучшением суффиксного бора, расходующим всего <tex>O( n|\Sigma|)</tex> памяти, является [[сжатое суффиксное дерево]].