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>.
