Изменения

При этом таблица для приведенной выше реализации выглядит так:{| 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>n</tex>. Тогда количество строк, в которых больше одного перехода будет <tex>O(n)</tex>. Поэтому, если не хранить массив вместо массива переходов для вершинхранить map<char, где такой переход единственный, integer> то можно получить оценку <tex>O(n^2 + n|\Sigma|)</tex>. Улучшением суффиксного бора, расходующим всего <tex>O( n|\Sigma|)</tex> памяти, является [[сжатое суффиксное дерево]].