228
правок
Изменения
→Хранение в памяти
==Хранение в памяти==
Пусть <tex>s \in \Sigma^*</tex>, <tex>\lvert s\rvert = n</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> памяти, является [[сжатое суффиксное дерево]].
[[Категория:Алгоритмы и структуры данных]]
[[Категория:Словарные структуры данных]]
