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

1. Хеши, префикс-функция, Z-функция
1. Хеши: вероятности; как выбрать модуль
2. С++ : можно умножать числа до 10¹⁸ по модулю. Java : BigInteger.
3. Найти номер строки в её суффиксном массиве
4. Для каждого префикса строки S проверить его периодичность
5. Найти в тексте s слово a, за ним слово b так, чтобы расстояние между вхождениями было минимально
6. Количество подпалиндромов строки за O(nlogn)
7. Цензор: Решаем задачу про текст и поиск словарных слов хешами
2. Бор
1. Цензор: пишем задачу dictionary [code]
2. Сортировка строк бором
3. Задачи на Ахо-Корасика
1. Для каждого словароного слова определить, входит ли оно в текст
2. Для каждого словароного слова посчитать количество вхождений в текст
3. Для каждого словароного слова найти самое левое вхождение в текст
4. [не успеем] Посчитать суммарное количество вхождений словарных слов в текст (количество пар "слово, позиция"). Текст online растёт.
5. [не успеем] Для каждого словарного слова найти все вхождения в текст за O(|text|+answer). Текст online растёт.
6. [не успеем] Найти минимальную по длине строку, которую можно прочитать двумя разными способами
7. [не успеем] За ход можно выписать префикс любой из данных строк. Нужно за минимальное число ходов выписать весь текст.
8. [не успеем] Поиск самой длинной подстроки словароного слова, входящей в текст.
9. [не успеем] За ход можно выписать подстроку любой из данных строк. Нужно за минимальное число ходов выписать весь текст.