Изменения

'''Суффиксный бор''' (англ. ''suffix trie'') {{---}} [[бор]], содержащий все суффиксы данной строки.

По определению, в суффиксном боре для строки <tex>s</tex> (где <tex>|s| = n</tex>) содержатся все строки <tex>s[1 \mathinner{\ldotp\ldotp} n], \dotsc, s[n \mathinner{\ldotp\ldotp} n]</tex>. Заметим, что если в суффиксном боре находится строка <tex>s[i \mathinner{\ldotp\ldotp} n]</tex>, то все её префиксы <tex>s[i \mathinner{\ldotp\ldotp} j]</tex> (<tex>i \leqslant j \leqslant n</tex>) уже содержатся в боре.

==Применение==

Суффиксный бор можно использовать для поиска подстроки в строке <tex>s</tex> тем же образом, что и для [[Бор#Поиск строки в бору|поиска строки в боре]]. Чтобы бор формально содержал все подстроки <tex>s</tex>, нужно пометить все его вершины терминальными, при этом корень будет соответствовать пустой строке <tex>\varepsilon</tex>.

'''map<char, Node>''' children

'''Node''' current = root

'''for''' c '''in''' s

'''if''' current.children[c] == <tex>\varnothing</tex>

current = current.children[c]

'''int''' n = s.size

'''for''' i = 1 '''to''' n

* [[Сжатое суффиксное дерево]]

*''Дэн Гасфилд'' — '''Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология''' — СПб.: Невский Диалект; БХВ-Петербург, 2003. — 654 с: ил.

[[Категория:Алгоритмы и структуры данных]]

[[Категория:Словарные структуры данных]]