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

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