Строки, бор и Ахо-Корасик (23 марта 2015)

1. Хеши, префикс-функция
1. Разбор задачи с VK-Cup, решение хешами
2. Решаем задачу про привидение Петю префикс функцией
3. Кодим задачу про привидение Петю и кубики хешами [code]
4. Решаем задачу про текст и поиск словарных слов хешами
5. Идея про то, что различных длин слов в словаре не более корня суммарной длины
6. Разбор задачи про архиватор через LCP
2. Бор
1. Пишем задачу dictionary [code]
2. Способы хранения бора
1. Традиционные способы хранения
2. Необычный способ хранения, O(N*(Sigma + L))
3. Хранение Splay деревом
3. Сортировка строк бором
4. map<string, type> = бор
5. Наибольший общий префикс двух строк из данного набора = LCA
6. Пишем бор, пишем суффиксное дерево за квадрат
7. Ахо-Корасик: ленивое написание (пишем getNext, getSuf)
8. Ахо-Корасик: написание с помощью bfs
3. Задачи на Ахо-Корасика
1. Для каждого словароного слова определить, входит ли оно в текст
2. Для каждого словароного слова посчитать количество вхождений в текст
3. Для каждого словароного слова найти самое левое вхождение в текст
4. Посчитать суммарное количество вхождений словарных слов в текст (количество пар "слово, позиция"). Текст online растёт.
5. Для каждого словарного слова найти все вхождения в текст за O(|text|+answer). Текст online растёт.
6. [не успеем] Найти минимальную по длине строку, которую можно прочитать двумя разными способами
7. За ход можно выписать префикс любой из данных строк. Нужно за минимальное число ходов выписать весь текст.
8. [не успеем] Поиск самой длинной подстроки словароного слова, входящей в текст.
9. За ход можно выписать подстроку любой из данных строк. Нужно за минимальное число ходов выписать весь текст.