Изменения

Определение суффиксного дерева не гарантирует, что такое дерево существует для любой строки <tex>s</tex>. Если один суффикс совпадает с префиксом другого суффикса, то построить суффиксное дерево, удовлетворяющее данному выше определению, невозможно, поскольку путь для первого суффикса не сможет закончиться в листе. Например, для строки <tex>xabxa</tex> суффикс <tex>xa</tex> является префиксом суффикса <tex>xabxa.</tex>. Во избежание этого в конце строки <tex>s</tex> добавляется символ, не входящий в исходный алфавит. Такой символ называется '''''защитным'''''. Как правило, защитный символ обозначается <tex>\$</tex>. Любой суффикс строки с защитным символом заканчивается в листе, т.к. этот символ не встречается в строке нигде, кроме позиции последнего символа. Далее <tex>n</tex> - длина строки <tex>s</tex> с защитным символом.