Алгоритмы на строках (СПБГУ МатМех, март 2013, спецкурс 344-й группы, лектор: Вова Смыкалов)

1. Постановка простейшей задачи: найти одну строку внутри другой.
2. Z-функция
1. определение
2. поиск подстроки в строке за O(n)
3. алгоритм вычисления за O(n)
4. доказательство времени работы
5. код на 4 строчки
6. решение задач
1. период строки за O(n)
2. количество различных подстрок строки за O(n²)
3. Префикс-функция (Алгоритм Кнута - Морриса - Пратта)
1. определение
2. поиск подстроки в строке за O(n)
3. алгоритм вычисления за O(n)
4. доказательство времени работы
5. код на 4 строчки
6. решение задач
1. период строки за O(n)
2. количество различных подстрок строки за O(n²)
4. Хеширование
1. основная идея
2. полиномиальный хеш
3. как вычислить для всех префиксов
4. пересчет для подстроки
5. коллизия хешей, теорема про sqrt(M)
6. какой выбирать модуль? P vs. 2³² vs. 2⁶⁴
7. построение antihash теста для 2⁶⁴
5. Бор
1. определение
2. добавление строки s в бор за O(|s|)
3. решение задачи "есть ли строка s в словаре" за O(|s|)
6. Анонсы
1. можно делать сжатый бор
2. алгоритм Ахо-Корасика