Изменения

[[Файл:Suffix_trie.png|thumb|right|Суффиксный бор для строки <tex>abbc</tex>]]'''Суффиксный бор''' (англ. ''suffix trie'') {{---}} — [[бор]], содержащий все суффиксы данной строки.

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

Суффиксный бор можно использовать для поиска подстроки в строке <tex>s</tex> (чтобы тем же образом, что и для [[Бор#Поиск строки в бору|поиска строки в боре]]. Чтобы бор формально содержал все подстроки <tex>s</tex>, нужно пометить все его вершины терминальными, при этом корень будет соответствовать пустой строке <tex>\varepsilon</tex>). Для поиска подстроки p в суффиксном боре нужно искать совпадения [[Файл:Syffix_trie_1.png|500px|thumb|center|Суффиксный бор для символов из p вдоль единственного пути в боре до тех пор, пока либо p не исчерпается, либо дальнейшее совпадение будет невозможным. Если p исчерпалось, то подстрока найдена за строки <tex>O(|p|)abbc</tex>, если дальнейшее совпадение невозможно, то p нет в суффиксном дереве.]]

===Свойства===[[Файл:aaabbb-suftrie.png|мини|400px|Суффиксный бор для строки «aaabbb»]]

* Можно можно использовать для поиска образца <tex>p</tex> в строке <tex>s</tex> за время <tex>O(\lvert |p\rvert|)</tex>.,* Можно можно построить за время <tex>O(n^2)</tex>, последовательно добавив все суффиксы <tex>s</tex>.,* Имеет имеет порядка <tex>n^2</tex> вершин в худшем случае. Например, для строки <tex>a^n b^n</tex> суффиксный бор будет содержать:: <tex>1</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 = \theta(n^2)</tex> вершин.</ul>

=== Реализация ===Зададим бор его корнем:<code style="display: inline-block"> '''struct ''' Trie: '''Node''' root</code>По каждому символу будем хранить переход в соответствующую вершину:<code style="display: inline-block"> '''struct''' Node: '''map<char, Node>''' children</code>При добавлении узла будем идти вниз по сыновьям и добавлять их, если необходимо:<code style="display: inline-block"> '''function''' add(s : '''string'''): int '''Node''' current = root '''for''' c '''in''' s '''if''' current.children[c] == <tex>\varnothing</tex> current.children[length^2c]= Node() current = current.children[alphabetc] trie number <tex/code>Чтобы построить суффиксный бор для некоторой строки, последовательно добавим в пустой бор все её суффиксы:<code style="display: inline-block"> \leftarrow '''function''' build(s : '''string'''): root = Node() '''int''' n = s.size '''for''' i = 0 '''to''' n - 1 add(s[i..n])</texcode>

'''Add'''(i, j)=== Оценки использования памяти === current Пусть мы построили суффиксный бор для строки <tex>s \in \leftarrowSigma^*</tex> 0 '''for''' (char c <tex>|s| = n</tex>). Из третьего свойства следует, что если хранить переходы суффиксного бора из каждой вершины как массив размера <tex>|\inSigma|</tex> s[i(по каждому символу — переход), j]то потребуется <tex>O(n^2 |\Sigma|)</tex> памяти. if (trie[current][c] Однако, заметим, что число ветвлений в не превышает числа листьев, что, в свою очередь, не превышает количества суффиксов. Количество суффиксов — <tex>\neq n</tex> -1, а значит число вершин, из которых ведет больше одного перехода, <tex>O(n) trie[current][c] </tex>. Поэтому, если в неветвящихся вершинах хранить только символ перехода и ребенка, то можно получить оценку <tex> O(n^2 + n|\leftarrowSigma|)</tex> number number++; current . Улучшением суффиксного бора, расходующим всего <tex>O( n|\leftarrowSigma|)</tex> trieпамяти, является [[currentсжатое суффиксное дерево][c].

'''Build'''(String s) '''for'''(int i = 0, i < n, i++)=См. также== Add(i, n)* [[Сжатое суффиксное дерево]]

==Хранение в памятиИсточники информации ==Пусть <tex>s \in \Sigma^*</tex>''Дэн Гасфилд'' — '''Строки, <tex>\lvert s\rvert = n</tex>. Из третьего свойства следует, что для хранения суффиксного бора деревья и последовательности в худшем случае потребуется <tex>O(n^2 |\Sigma|)</tex> памяти. Например, если строка состоит из всех символов алфавита. В таком случаи из корня дерева будет выходить n ветвей, алгоритмах: Информатика и в каждой из них будет O(n) вершинвычислительная биология''' — СПб.Количество разветвлений будет равно количеству суффиксов: Невский Диалект; БХВ-Петербург, так как каждый лист соответствует единственному суффиксу2003. Количество суффиксов <tex>n</tex>. Тогда количество вершин, в которых больше одного перехода будет <tex>O(n)</tex>. Поэтому, если вместо массива переходов для вершин хранить map<char, integer>, то можно получить оценку <tex>O(n^2 + n|\Sigma|)</tex>. Улучшением суффиксного бора, расходующим всего <tex>O( n|\Sigma|)</tex> памяти, является [[сжатое суффиксное дерево]]— 654 с: ил.