130
правок
Изменения
→Свойства: изменил оформление списка; обернул переменные в <tex>
* можно использовать для поиска образца <tex>p</tex> в строке <tex>s</tex> за время <tex>O(|p|)</tex>,
* можно построить за время <tex>O(n^2)</tex>, последовательно добавив все суффиксы <tex>s</tex>,
* имеет порядка <tex>n^2</tex> вершин в худшем случае. Например, для строки <tex>a^n b^n</tex> суффиксный бор будет содержать:<!---->: <ultex>1<li/tex>1 корневую вершину,: <!----tex>n<li/tex> n вершин для суффикса <tex>b^n</tex>,: <!----tex>n<li/tex> n вершин для подстроки <tex>a^n</tex>, у каждой по <tex>n </tex> вершин для соответствующего суффикса <tex>b^n</tex>.</ulstyle="list-style: none;"><!-- Вики-разметка не может в продолжение элемента списка после вложенного списка — очень жаль.--li>итого <tex>1 + 2n + n^2 = (n+1)^2 = O(n^2)</tex> вершин.</ul>
<br clear="all">
