Строки-3, бор, Ахо-Корасик (21 апреля)

  1. Несжатый бор
    1. Хранение: массив, список, map<int,int>, unordered_map<int,int>, Splay-дерево, читерский способ
    2. Сортировка строк
    3. map<string, T>
  2. Сжатый бор. Суффиксное дерево.
    1. Хранение сжатого бора
    2. Построение суффиксного дерева за [Time=O(n2), Space=O(n)]
    3. Смысл суффиксного дерева: для каждой подстроки знаем длину, количество вхождений, самое левое вхождение, самое правое вхождение
    4. LCA в суфф.дереве = LCP суффиксов
    5. Суффиксный массив + LCP → суффиксное дерево за O(n)
    6. Суффиксный массив + LCP ← суффиксное дерево за O(n)
  3. Задача про поиск словарных слов в тексте (W = max|Si|, D = количество различных|Si|)
    1. Решение хешами (W*|T|, D*|T|, D ≤ 2sqrt(sumLen))
    2. Решение бором (W*|T|)
  4. Ахо-Корасик
    1. Определяем суффиксные ссылки, пример.
    2. Использование для проверки, лежит ли в тексте хотя бы одно словарное слово
    3. Использование для нахождения для каждого словарного слова "количества, сколько раз это слово лежит в тексте".
    4. Построение bfs-ом
    5. [не успеем] Ленивое построение