Строки: бор (26 апреля 2016)

  1. Бор.
    1. Способы хранения. Array, list, treeSet, hashSet, splaySet.
    2. Сортировка бором.
  2. Алгоритм Ахо-Корасик
    1. Определение суфф ссылок.
    2. Вычисление, как в префикс-функции. Порядок вычисления: bfs. Фиктивная вершина.
    3. Доказательство времени работы O(∑leni).
    4. Полный автомат: вычисление next[v,char], использование для получения суфф ссылок за O(1).
    5. Применение к поиску строки в тексте. Добавляем isEnd[v], доказываем, что всегда найдём строку.
--- Перерыв ---
  1. Суфф дерево
    1. Сжатый бор. Хранение. Информацию про ребро можно хранить от вершины.
    2. Суфф дерево за [T=O(n2), M=O(n)]
    3. Задача "поиск подстроки в тексте" за O(|s|) суфф деревом.
  2. Алгоритм Укконена построения суфф дерева в online
    1. Простая версия за [T=O(n2), M=O(n)]: храним указатели на концы суффиксов
    2. Суффиксы-листья растут сами
    3. Жизненный цикл суффикса (1) идёт по дереву, (2) разветвился, (3) саморастущий лист.
    4. Основная лемма: если суффикс неразветвился, то все более короткие тоже неразветвились
    5. Алгоритм: храним указатель на самый длинный не разветвившийся, пересчитываем его.
    6. Подсчёт суфф ссылки. Линейность времени работы.
  3. Тонкости реализации
    1. Фиктивная вершина помогает два раза: всегда есть суфф ссылка, всегда будет (1)-суффикс
    2. При создании новой суфф ссылки, может оказаться, вершина ещё не создана... но мы уже знаем её номер.
    3. ???
  4. Суфф массив ↔ суфф дерево
    1. Суфф массив + LCP → суфф дерево. O(n).
    2. Cуфф дерево → Суфф массив + LCP. O(n).