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

1. Суффиксный массив за O(n)
2. Сжатый бор, суффиксное дерево, построение за O(n2)
3. Суффиксные массив ↔ дерево
4. Задачи на суффдерево

1. Поиск подстроки в тексте за O(|s|)
2. Число различных подстрок
3. Поиск общей подстроки k строк
4. LZSS (архиватор)
5. max глубина суфф дерева, если суммарная длина строк равна m?

5. Построение Суффиксного дерево за O(n) (Укконен)

1. Простая версия за [T=O(n2), M=O(n)]: храним указатели на концы суффиксов. Пример: ababbaa.
2. Суффиксы-листья растут сами. Два варианта реализации: наростить сразу до конца, или хранить ребро [l,∞]
3. Жизненный цикл суффикса (1) идёт по дереву, (2) разветвился, (3) саморастущий лист.
4. Основная лемма: если суффикс не разветвился, то все более короткие тоже не разветвились.
5. Алгоритм: храним указатель на самый длинный не разветвившийся, пересчитываем его.
6. Суффссылки. Лемма: суффиксная ссылка вершины − вершина
7. Подсчёт суфф ссылки. Линейность времени работы.
8. Пример построения на строке "ababbaabbc".
9. Псевдокод.

6. Дополнительно: дерево палиндромов