276
правок
Изменения
м
Нет описания правки
'''Суффиксный бор''' (англ. ''suffix trie'') — [[бор]], содержащий все суффиксы данной строки.
По определению, в суффиксном боре для строки <tex>s</tex> (где <tex>|s| = n</tex>) содержатся все строки <tex>s[1 \mathinner{\ldotp\ldotp} ldots n], \dotsc, s[n \mathinner{\ldotp\ldotp} ldots n]</tex>. Заметим, что если в суффиксном боре находится строка <tex>s[i \mathinner{\ldotp\ldotp} ldots n]</tex>, то все её префиксы <tex>s[i \mathinner{\ldotp\ldotp} ldots j]</tex> (<tex>i \leqslant j \leqslant n</tex>) уже содержатся в боре.
==Применение==
Суффиксный бор можно использовать для поиска подстроки в строке <tex>s</tex> тем же образом, что и для [[Бор#Поиск строки в бору|поиска строки в боре]]. Чтобы бор формально содержал все подстроки <tex>s</tex>, нужно пометить все его вершины терминальными, при этом корень будет соответствовать пустой строке <tex>\varepsilon</tex>.
: <tex>n</tex> вершин для суффикса <tex>b^n</tex>,
: <tex>n</tex> вершин для подстроки <tex>a^n</tex>, у каждой по <tex>n</tex> вершин для соответствующего суффикса <tex>b^n</tex>.
<ul style="list-style: none;"><li>итого <tex>1 + 2n + n^2 = (n+1)^2 = O\theta(n^2)</tex> вершин.</ul>
=== Реализация ===
