Строки: суффиксное дерево (26 октября 2017)

  1. Бор
    1. Способы хранения. Array, list, treeSet, hashSet, splaySet.
    2. Сортировка бором

  2. Алгоритм Ахо-Корасик
    1. Постановка задачи, решение бором в лоб за O(|text|*max|si|)
    2. Определение суфф ссылок.
    3. Вычисление суфф ссылок и связь с префикс-функцией. Порядок вычисления: bfs. Фиктивная вершина.
    4. Доказательство времени работы O(∑leni).
    5. Полный автомат: вычисление next[v,char], использование для получения суфф ссылок за O(1).
    6. Применение к поиску строки в тексте. Добавляем isEnd[v], доказываем, что всегда найдём строку.
− Перерыв −
  1. Суфф дерево
    1. Сжатый бор. Хранение. Информацию про ребро можно хранить от вершины, куда ведёт ребро.
    2. Суфф дерево за [T=O(n2), M=O(n)]
    3. Задача "поиск подстроки в тексте" за O(|s|) суфф деревом.

  2. Суфф массив ↔ суфф дерево
    1. Суфф массив + LCP → суфф дерево. O(n).
    2. Cуфф дерево → Суфф массив + LCP. O(n).

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

  4. Тонкости реализации
    1. Фиктивная вершина помогает два раза: всегда есть суфф ссылка, всегда будет (1)-суффикс
    2. При создании новой суфф ссылки, может оказаться, вершина ещё не создана... но мы уже знаем её номер (наша нумерация − автоинкремент).
    3. После перехода по суфф ссылке идти вниз нужно, пока не дойдём до вершины, до которой "чуть-чуть не достаём".