80
правок
Изменения
→Определение
{{Определение
|definition =
'''Суффиксное дерево''' (сжатое суффиксное дерево) <tex>T</tex> для строки <tex>s</tex> (где <tex>|s| = n</tex>) {{---}} дерево с <tex>n</tex> листьями, каждая обладающее следующими свойствами:*Каждая внутренняя вершина которого дерева имеет не меньше двух детей, а каждое ;*Каждое ребро помечено непустой подстрокой строки <tex>s</tex>. Два ;*Никаких два ребра, выходящие из одной вершины, не могут иметь пометок, начинающихся с одного и того же символа;*Дерево должно содержать все суффиксы строки <tex>s</tex>, причем каждый суффикс заканчивается точно в листе и нигде кроме него.
}}
Рассмотрим дерево для строки <tex>xabxa</tex>. У него суффикс <tex>xa</tex> является префиксом суффикса <tex>xabxa</tex>, значит, этот суффикс не закачивается в листе. Для решения проблемы в конце строки <tex>s</tex> добавляют символ, не входящий в исходный алфавит: '''''защитный''''' символ. Как правило, это <tex>\$</tex>. Любой суффикс строки с защитным символом действительно заканчивается в листе и только в листе.
