130
правок
Изменения
→Свойства: добавлен пример, на котором достигается оценка количества вершин
==Свойства==
Суффиксный бор для строки <tex>s</tex>:
* Можно использовать для поиска образца <tex>p</tex> в строке <tex>s</tex> за время <tex>O(\lvert |p\rvert|)</tex>.
* Можно построить за время <tex>O(n^2)</tex>, последовательно добавив все суффиксы <tex>s</tex>.
* Имеет порядка <tex>n^2</tex> вершин в худшем случае. Например, для строки, каждый символ в которой уникален, суффиксный бор будет содержать <tex>1 + \sum\limits_{k=1}^n k = 1 + \frac{n \cdot (n+1)}{2}</tex> вершин.
== Реализация ==
