322
правки
Изменения
Новая страница: «{{В разработке}} '''Суффиксный бор''' (suffix trie) - бор, содержащий все суффиксы данной строки. П…»
{{В разработке}}
'''Суффиксный бор''' (suffix trie) - [[бор]], содержащий все суффиксы данной строки.
По определению, в суффиксном боре для строки s содержатся все строки <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>\epsilon)</tex>.
==Свойства==
Суффиксный бор для строки <tex>s</tex>:
* Можно использовать для поиска образца <tex>p</tex> в строке <tex>s</tex> за время <tex>O(|p|)</tex>.
* Можно построить за время <tex>O(|s|^2)</tex>, последовательно добавив все суфиксы <tex>s</tex>.
* Имеет порядка <tex>n^2</tex> вершин.
==Хранение в памяти==
Пусть <tex>s \in \Sigma^*</tex>. Из третьего свойства следует, что для хранения суффиксного бора в худшем случае потребуется <tex>O(n^2 |\Sigma|)</tex> памяти. Если не хранить массив переходов по символам для вершин, где такой переход единственный, получаем оценку <tex>O(n^2 + n|\Sigma|)</tex>. Улучшением суффиксного бора, расходующим всего <tex>O( n|\Sigma|)</tex> памяти, является [[Сжатое суффиксное дерево|сжатый суффиксный бор]].
'''Суффиксный бор''' (suffix trie) - [[бор]], содержащий все суффиксы данной строки.
По определению, в суффиксном боре для строки s содержатся все строки <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>\epsilon)</tex>.
==Свойства==
Суффиксный бор для строки <tex>s</tex>:
* Можно использовать для поиска образца <tex>p</tex> в строке <tex>s</tex> за время <tex>O(|p|)</tex>.
* Можно построить за время <tex>O(|s|^2)</tex>, последовательно добавив все суфиксы <tex>s</tex>.
* Имеет порядка <tex>n^2</tex> вершин.
==Хранение в памяти==
Пусть <tex>s \in \Sigma^*</tex>. Из третьего свойства следует, что для хранения суффиксного бора в худшем случае потребуется <tex>O(n^2 |\Sigma|)</tex> памяти. Если не хранить массив переходов по символам для вершин, где такой переход единственный, получаем оценку <tex>O(n^2 + n|\Sigma|)</tex>. Улучшением суффиксного бора, расходующим всего <tex>O( n|\Sigma|)</tex> памяти, является [[Сжатое суффиксное дерево|сжатый суффиксный бор]].
