Сжатое суффиксное дерево

Определение:

Пусть дана строка [math]S[/math], [math]|S| = m[/math]. Суффиксное дерево [math]T[/math] для строки [math]S[/math] - ориентированное дерево с корнем, имеющее ровно [math]m[/math] листьев, занумерованных от [math]1[/math] до [math]m[/math]. Каждая внутренняя вершина, отличная от корня, имеет не меньше двух детей, а каждая дуга помечена непустой подстрокой строки [math]S[/math]. Никакие две дуги не могут иметь пометок, начинающихся с одного и того же символа.

Главная особенность суффиксного дерева заключается в том, что для каждого листа [math]i[/math] конкатенация меток дуг на пути от корня к листу [math]i[/math] в точности составляет суффикс строки [math]S[/math], который начинается в позиции [math]i[/math], то есть [math]S[i..m][/math].

Определение суффиксного дерева не гарантирует, что такое дерево существует для любой строки [math]S[/math]. Если один суффикс совпадает с префиксом другого суффикса, то построить суффиксное дерево, удовлетворяющее данному выше определению, невозможно, поскольку путь для первого суффикса не сможет закончиться в листе. Например, для строки [math]xabxa[/math] суффикс [math]xa[/math] является префиксом суффикса [math]xabxa[/math]. Во избежание этого в конце строки [math]S[/math] добавляется символ, не входящий в исходный алфавит. Такой символ называется защитным. Как правило в качестве защитного символа используется [math]\$[/math].