День 4. Строки: хеши, бор, рыбалка.
- Полиномиальные хеши
- Идея для сравнения подстрок строки
- Поиск подстроки в строке с O(1) памяти: Рабин-Карп
- Выбор пары P, MOD (модуля и точки): MOD − простой, P − случайное.
- Поиск подстроки в строке, вероятность ошибки: n/MOD
- Подсчёт числа различных подстрок, вероятность ошибки: n3/MOD или n4/MOD, если извращаться
- Считает два хеша − (P1, MOD1) и (P2, MOD1). Можно брать MOD1 = MOD2.
int128_t
в помощь
- Хеш-таблица
- Списки (цепочки):
vector<int> table[SIZE]
, добавление, поиск, удаление
- Открытая адресация:
int table[SIZE]
, добавление, поиск, удаление
- Поиск общей подстроки за O(nlogn): бинпоиск + хеш-таблица
- Бор и Ахо-Корасик
- Несжатый бор. Хранение рёбер: массив, map, хеш-таблица.
- Формулировка задачи: найти словарное слово в тексте
- Решение за O(|T|*max|Si|) = построили бор, от каждой вершины спускаемся по бору.
- Вспоминаем поиск подстроки в строке: мы только что сделали аналог Z-функции, сделаем теперь аналог Префикс-функции... хотим поддерживать самую глубокую вершину бора vi : string(root, vi) − суффикс s.substring(0, i)
- Ахо-Корасик #1: дан бор, для каждой пары v, char посчитать next[v, char].
- Ахо-Корасик #2: дан массив строк, не будем строить полный автомат, построим только суффссылки.
- Построение, применение для поиска подстроки. Не забыть пометить конечные вершины.
- Задачи
map<string, int>
- Дан массив строк, запрос: "количество строк, кончающихся на t"
- Дан массив строк, запрос: "количество строк, начинающихся на s, кончающихся на t"
- Даны текст и словарь: для каждого слова словаря посчитать, сколько раз оно встречается в тексте