Структуры данных

  1. Запрос на прямоугольнике.
  2. 2D дерево отрезков от N точек с NlogN памятью (дерево отрезков, в каждой вершине еще одно дерево отрезков)
  3. Вертикальный путь в дереве = прямоугольник на плоскости [все запросы в меняющемся дереве за O(log2N)]
  4. Heavy-Light decomposition дерева (покрытие путями, для каждого пути хранится дерево отрезков) [все запросы в меняющемся дереве за O(log2N)]

Задачи на пройденные структуры данных

  1. Persistent СНМ

Классика

  1. Z-функция
  2. Префикс-функция
  3. Решение задач Z и Prefix функциями
    1. Поиск подстроки в тексте
    2. Период строки
    3. Наименьший номер строки массиве ее циклических сдвигов
    4. Количество подстрок, входящих в текст 2 раза.

Алгоритм Ахо-Корасик

  1. Задача: найти подстроку из словаря в тексте за O(|Text|)
  2. Складываем строки в несжатый бор
  3. Определяем suf-ссылку
  4. Строим полный автомат

Строки. Хэши.

  1. Полиномиальный хэш. Hash(s) - псевдослучайное число в диапозоне от 0 до 264 - 1.
  2. Коллизии, обработка коллизий, вероятность возникновения коллизий.
  3. Сравнение строк на равенство за O(1).
  4. Полиномиальный хэш применим к произвольному объекту. Пример: отсечение в переборе с помощью set <long long>.
  5. Решение задач хэшами и хэш-таблицами
    1. Наибольшая общая подстрока.
    2. Поиск словарных слов в тексте.
    3. Количество подстрок строки.

Строки. Суффиксный массив.

  1. Определение. Построение в лоб за O(N2logN). Реальное время работы уже O(NlogN).
  2. Сравнение строк на больше и меньше за O(logN) хэшами.
  3. Построение суффиксного массива за O(Nlog2N) в худшем случае.
  4. Построение LCP для суффиксного массива за O(NlogN).
  5. Решение задачи поиска подстроки в тексте с помощью суф. массива за предподсчет O(|Text|*log2) и запрос за O(|S|*log|Text|).

LCP

  1. Предподсчет LCP[i,j] динамикой за O(N2)
  2. LCP[i,j] = минимум на отрезке, если построить суф. массив
  3. LCP[i,j] считается за O(logN) хэшами

Суф. дерево

  1. Опередление.
  2. Сжатое суф. дерево.
  3. Алгоритм построения за O(N2).
  4. Решение задач суф.деревом
    1. Количество подстрок
    2. Количество общихподстрок
    3. Количество подпалиндромов