День 4. Строки: хеши, бор, рыбалка.

  1. Полиномиальные хеши
    1. Идея для сравнения подстрок строки
    2. Поиск подстроки в строке с O(1) памяти: Рабин-Карп
    3. Выбор пары P, MOD (модуля и точки): MOD − простой, P − случайное.
    4. Поиск подстроки в строке, вероятность ошибки: n/MOD
    5. Подсчёт числа различных подстрок, вероятность ошибки: n3/MOD или n4/MOD, если извращаться
    6. Считает два хеша − (P1, MOD1) и (P2, MOD1). Можно брать MOD1 = MOD2.
    7. int128_t в помощь

  2. Хеш-таблица
    1. Списки (цепочки): vector<int> table[SIZE], добавление, поиск, удаление
    2. Открытая адресация: int table[SIZE], добавление, поиск, удаление
    3. Поиск общей подстроки за O(nlogn): бинпоиск + хеш-таблица

  3. Бор и Ахо-Корасик
    1. Несжатый бор. Хранение рёбер: массив, map, хеш-таблица.
    2. Формулировка задачи: найти словарное слово в тексте
    3. Решение за O(|T|*max|Si|) = построили бор, от каждой вершины спускаемся по бору.
    4. Вспоминаем поиск подстроки в строке: мы только что сделали аналог Z-функции, сделаем теперь аналог Префикс-функции... хотим поддерживать самую глубокую вершину бора vi : string(root, vi) − суффикс s.substring(0, i)
    5. Ахо-Корасик #1: дан бор, для каждой пары v, char посчитать next[v, char].
    6. Ахо-Корасик #2: дан массив строк, не будем строить полный автомат, построим только суффссылки.
    7. Построение, применение для поиска подстроки. Не забыть пометить конечные вершины.

  4. Задачи
    1. map<string, int>
    2. Дан массив строк, запрос: "количество строк, кончающихся на t"
    3. Дан массив строк, запрос: "количество строк, начинающихся на s, кончающихся на t"
    4. Даны текст и словарь: для каждого слова словаря посчитать, сколько раз оно встречается в тексте