Изменения

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

По определению, в суффиксном боре для строки <tex>s</tex>, (где <tex>|\lvert s|\rvert=n</tex> ) содержатся все строки <tex>s[1..n], ..., s[n..n]</tex>. Сделаем следующее наблюдение: если в суффиксном боре находится строка <tex>s[i..n]</tex>, то все ее префиксы <tex>s[i..j], i \le j \le n</tex> уже содержатся в нашем боре. Значит, суффиксный бор можно использовать для поиска всех подстрок строки <tex>s</tex> (чтобы бор формально содержал все подстроки <tex>s</tex>, нужно пометить все его вершины терминальными, при этом корень будет соответствовать пустой строке <tex>\varepsilon</tex>).

* Можно использовать для поиска образца <tex>p</tex> в строке <tex>s</tex> за время <tex>O(|\lvert p|\rvert)</tex>.* Можно построить за время <tex>O(|\lvert s|\rvert^2)</tex>, последовательно добавив все суффиксы <tex>s</tex>.* Имеет порядка <tex>|\lvert s|\rvert^2</tex> вершин.

Пусть <tex>s \in \Sigma^*</tex>, <tex>|\lvert s| \rvert = n</tex>. Из третьего свойства следует, что для хранения суффиксного бора в худшем случае потребуется <tex>O(n^2 |\Sigma|)</tex> памяти. Если не хранить массив переходов по символам для вершин, где такой переход единственный, то можно получить оценку <tex>O(n^2 + n|\Sigma|)</tex>. Улучшением суффиксного бора, расходующим всего <tex>O( n|\Sigma|)</tex> памяти, является [[сжатое суффиксное дерево]].