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

vb = <font color=green>[Ваня]</font>
sk = <font color=darkblue>[Сережа.K]</font>
sm = <font color=darkred>[Сережа.М]</font>


# $sm$ Декартово дерево
## Остатки

# $vb$ Строки, строки, строки
## Хеши 
### Сравнение на равенство за O(1)
### Сравнение на больше-меньше за O(logn)
### Выбор модуля. Реализация: как и в частичных суммах h[0] = 0
### Решение задач
## Хеш-таблица
### Открытая адресация (быстро, но только добавление)
### Списки 
## Задачи
### LCP(i, j) за O(logn) хешами
### Наибольшая общая подстрока за O(nlogn)
### LCP(i, j) для всех i, j динамикой за O(n^2)
## Бор
### Реализация через <code>next[N][26]</code>
### Реализация через списки, хеш-таблицу
### Сжатый бор: ребро = подстрока исходной строки
### Суф.дерево, построение за O(n^2) и O(n) памяти, число различных подстрок

v = <code>vector&lt;int>(n)</code>
vn = <code>vector&lt;int>(n)</code>

# $sk$ С/C++ 
## $vn$ <code>= {int *a, size\_t n, size\_t size}</code>
## Один $vn$. Он быстрый как <code>new int[n]</code>. Мятный как орбит-мята.
## Создадим 10^7 векторов, в каждый сделаем 4 раза push\_back. Долго?
### reserve(4), resize(4)
### operator new, operator delete
### замеряем время освобождения памяти: оборачиваем массив векторов в объект