День 6. Укконен.

1. С++
1. Битовое сжатие внутри структуры
2. pragma pack
3. sizeof от массива, указателя, вектора


2. Сжатый бор
1. Хранение: на ребре написано подстрока
2. Хранение: или struct Node { Edge next[26]; }; , или struct Node { Edge e; int next[26]; };
3. Суффдерево. Построение суффдерева за квадрат.


3. Задачи
1. Число различных подстрок за O(n)
2. Максимальный рефрен (len*count) за O(n)
3. Вхождение строки в текст, и число вхождений, и первое, и последнее
4. Общая подстрока двух строк
5. LZSS


4. Связь дерева и массива
1. Дерево → массив+LCP за O(n)
2. Массив+LCP → дерево за O(n)


5. Укконен
1. Онлайн, строка растёт s → sa
2. Версия за квадрат: храним концы всех суффиксов
3. Первая оптимизация: листья растут сами
4. Главная идея: первым разветвится самый длинный не разветвившийся суффикс
5. Текущая версия алгоритма: помним ссылку на позицию в боре самого длинного суффикса. Как только он разветвился, создали бесконечный лист и за O(n) нашли позицию следующего суффикса.
6. Как быстро находить следующий суффикс? Суффссылка от отца + спуск.
7. Вычисление суффссылки новой вершины.
8. Доказательство линейности времени работы.
9. Тонкости реализации: фиктивная вершина, разбор всех случаев во время спуска, создание суффссылки на ещё не существующую вершину.
10. Примеры: aaaaab, ababbabaac