80
правок
Изменения
→Существование сжатого суффиксного дерева
'''Суффиксное дерево''' (сжатое суффиксное дерево) <tex>T</tex> для строки <tex>s</tex> (где <tex>|s| = n</tex>) {{---}} ориентированное дерево с <tex>n</tex> листьями, каждая внутренняя вершина которого имеет не меньше двух детей, а каждое ребро помечено непустой подстрокой строки <tex>s</tex> и символом, с которого начинается эта подстрока. При этом два ребра, выходящие из одной вершины, не могут иметь одинаковых символьных пометок. Такое дерево содержит все суффиксы строки <tex>s</tex>: для каждого листа <tex>i</tex> конкатенация подстрок на ребрах пути от корня к этому листу составляет суффикс, который начинается в позиции <tex>i</tex>, то есть <tex>s[i..n]</tex>. Иными словами, каждый суффикс строки <tex>s</tex> заканчивается точно в листе и нигде кроме листа, как и в суффиксном боре.
==Существование сжатого суффиксного дереваЗащитный символ==
[[Файл:Suffix_tree_3.png|thumb|right|Суффиксное дерево для строки <tex>xabxa</tex> с защитным символом]]
Определение суффиксного дерева не гарантирует, что такое дерево существует для любой строки <tex>s</tex>. Если один суффикс строки совпадает с префиксом другого суффикса, то построить суффиксное дерево, удовлетворяющее данному выше определению, невозможно, поскольку путь для первого суффикса не сможет закончиться в листе. Например, для строки <tex>xabxa</tex> суффикс <tex>xa</tex> является префиксом суффикса <tex>xabxa.</tex> Во избежание этого в конце строки <tex>s</tex> добавляется символ, не входящий в исходный алфавит. Такой символ называется '''''защитным'''''. Как правило, защитный символ обозначается это <tex>\$</tex>. Любой суффикс строки с защитным символом заканчивается в листе, т.к. этот символ он не встречается в строке нигде, кроме позиции последнего символа.
Далее <tex>n</tex> - длина строки <tex>s</tex> с защитным символом.
