ЛКШ 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. Дополнительно: дерево палиндромов