## ЛКШ 2018, 7-й день, Строки-1 (Илья Подуременных)

1. Бор

1. Описание. Способы хранения. Array, list, map, hashMap, splay. Хеш-таблицу выгодно хранить одну большую.
2. За сколько работает сортировка бором? O(∑i leni × log|Σ|), за линию нельзя, т.к. нельзя вообще.

2. Алгоритм Ахо-Корасик

1. Постановка задачи, решение бором в лоб за O(|text|*max|si|). Решение хеш-таблицей за то же время.
2. Как оптимизировать решение бором? Аналогия с поиском подстроки в строке за O(nm) и префикс-функцией, определение суффссылок.
3. Вычисление суфф ссылок. Порядок вычисления: bfs. Фиктивная вершина.
4. Доказательство времени работы O(∑leni): для каждой строки суммарное время вычисления по всем символам строки O(leni).
5. Тонкость оценки времени работы: не O(размера бора), а именно O(суммы длин строк)
6. Полный автомат: вычисление next[v,char] для всех char, использование для получения суфф ссылок за O(1). Практика: ленивое вычисление.
7. Применение к поиску строки в тексте. Добавляем isEnd[v], доказываем, что всегда найдём строку; пример (s1=ababac, s2=bab : t=ababax).

3. Суффиксный массив

1. Напоминание, что суффмассив весит O(n) и мы его умеем строить хешами за O(nlog2n)
2. Поиск подстроки в тексте за O(|s|log|T|) и O(|s|+log|s|log|T|)

4. Суффиксный массив за O(nlogn)

1. Сортируем циклические сдвиги строки s#
2. За O(Σ + n2) цифровой сортировкой
3. От k переходим не к k+1, а к 2k, внутри используем сортировку подсчётом для пар, уже отсортированных по второй половине
4. Учимся писать. Должно получиться что-то типа моего
5. Касаи за O(n) для подсчёта LCP

5. Задачи на суффмассив

1. Число различных подстрок
2. Поиск общей подстроки k строк
3. LZSS (архиватор)
4. Поиск подстроки в тексте за O(|s| + log|text|)

1. Собственно алгоритм: SM ≥ max(min(SL, ML), min(SR, MR))
2. Вычисление ML и MR за O(1) с предподсчётом за O(n): дерево отрезков
3. Доказательство того, что при SM++ увеличится на следующей фазе max(SL, SR)

6. Задачи на тему Ахо-Корасик (в конце, т.к. имеет меньший приоритет)

1. Поиск подстроки в боре
2. Посчитать для каждого словарного слова, сколько раз оно встречается в тексте, найти самое левое и самое правое вхождения
3. Разбить строку длины 105 на словарные слова суммарной длины 105.