Изменения

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