$ ЛКШ 2018, 8-й день, Строки-2 (Сергей Копелиович)

# Суффиксный массив за O(n)
# Сжатый бор, суффиксное дерево, построение за O(n^2)
# Суффиксные массив &harr; дерево

<br>
# Задачи на суффдерево
## Поиск подстроки в тексте за O(|s|)
## Число различных подстрок
## Поиск общей подстроки k строк
## LZSS (архиватор)
## max глубина суфф дерева, если суммарная длина строк равна m?

<br>
# Построение Суффиксного дерево за O(n) (Укконен)
## Простая версия за [T=O(n^2), M=O(n)]: храним указатели на концы суффиксов. Пример: ababbaa.
## Суффиксы-листья растут сами. Два варианта реализации: наростить сразу до конца, или хранить ребро [l,&infin;]
## Жизненный цикл суффикса (1) идёт по дереву, (2) разветвился, (3) саморастущий лист.
## Основная лемма: если суффикс не разветвился, то все более короткие тоже не разветвились.
## Алгоритм: храним указатель на самый длинный не разветвившийся, пересчитываем его.
## Суффссылки. Лемма: суффиксная ссылка вершины -- вершина
## Подсчёт суфф ссылки. Линейность времени работы.
## Пример построения на строке "ababbaabbc".
## Псевдокод.

<br>
# Дополнительно: дерево палиндромов