Изменения

[[Суффиксный бор|Суффиксный бор]] {{---}} удобная структура данных для поиска подстроки в строке, но она занимает много места в памяти. Рассмотрим в боре все пути от <tex>u</tex> до <tex>v</tex>, в которых у каждой вершины только один сын. Такой путь можно сжать до ребра <tex>u v</tex>, записав на нем все встречающиеся на пути символы, которые являются подстрокой исходной строки. Для хранения ее на ребре обычно используют индексы <tex>l, r</tex> начала и конца. Получилось '''сжатое суффиксное дерево'''.

Заметим, что для хранения на ребре подстроки используют индексы <tex>l, r</tex> ее начала и конца в исходной строке, а не хранят саму строку. Представим теперь дерево как массив <tex>[|V|*|\Sigma|]</tex>, где <tex>|V|</tex> {{---}} количество вершин в дереве, <tex>|\Sigma|</tex> - мощность алфавита. Для любого суффиксного дерева верна предыдущая лемма (у каждой вершины по определению не менее двух детей), значит, <tex>|V| = O(2*n)</tex>. Каждая <tex>[i][j]</tex> ячейка содержит информацию о том, в какую вершину ведет <tex>i-</tex>ое ребро по <tex>j-</tex>ому символу и индексы <tex>l, r</tex>. Итак, дерево занимает <tex>O(n*|\Sigma|)</tex> памяти.