Строки: хеши и бор

1. [Сережа.М] Декартово дерево
1. Остатки
2. [Ваня] Строки, строки, строки
1. Хеши
1. Сравнение на равенство за O(1)
2. Сравнение на больше-меньше за O(logn)
3. Выбор модуля. Реализация: как и в частичных суммах h[0] = 0
4. Решение задач
2. Хеш-таблица
1. Открытая адресация (быстро, но только добавление)
2. Списки
3. Задачи
1. LCP(i, j) за O(logn) хешами
2. Наибольшая общая подстрока за O(nlogn)
3. LCP(i, j) для всех i, j динамикой за O(n²)
4. Бор
1. Реализация через next[N][26]
2. Реализация через списки, хеш-таблицу
3. Сжатый бор: ребро = подстрока исходной строки
4. Суф.дерево, построение за O(n²) и O(n) памяти, число различных подстрок
3. [Сережа.K] С/C++
1. vector<int>(n) = {int *a, size_t n, size_t size}
2. Один vector<int>(n). Он быстрый как new int[n]. Мятный как орбит-мята.
3. Создадим 10⁷ векторов, в каждый сделаем 4 раза push_back. Долго?
1. reserve(4), resize(4)
2. operator new, operator delete
3. замеряем время освобождения памяти: оборачиваем массив векторов в объект