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

# Бор
## Описание. Способы хранения. Array, list, map, hashMap, splay. Хеш-таблицу выгодно хранить одну большую.
## За сколько работает сортировка бором? O(&Sum;_i len_i &times; log|&Sigma;|), за линию нельзя, т.к. нельзя вообще.

<br>
# Алгоритм Ахо-Корасик
## Постановка задачи, решение бором в лоб за O(|text|*max|s_i|). Решение хеш-таблицей за то же время.
## Как оптимизировать решение бором? Аналогия с поиском подстроки в строке за O(nm) и префикс-функцией, определение суффссылок.
## Вычисление суфф ссылок. Порядок вычисления: bfs. Фиктивная вершина.
## Доказательство времени работы O(&sum;len_i): для каждой строки суммарное время вычисления по всем символам строки O(len_i).
## Тонкость оценки времени работы: не O(размера бора), а именно O(суммы длин строк)
## Полный автомат: вычисление next[v,char] для всех char, использование для получения суфф ссылок за O(1). Практика: ленивое вычисление.
## Применение к поиску строки в тексте. Добавляем isEnd[v], доказываем, что всегда найдём строку; пример (s_1=ababac, s_2=bab : t=ababax).

<br>
# Суффиксный массив
## Напоминание, что суффмассив весит O(n) и мы его умеем строить хешами за O(nlog^2n)
## Поиск подстроки в тексте за O(|s|log|T|) и O(|s|+log|s|log|T|)
# Суффиксный массив за O(nlogn)
## Сортируем циклические сдвиги строки s#
## За O(&Sigma; + n^2) цифровой сортировкой
## От k переходим не к k+1, а к 2k, внутри используем сортировку подсчётом для пар, уже отсортированных по второй половине
## Учимся писать. Должно получиться что-то типа @link:моего:https://ejudge.lksh.ru/A/examples/suffarray.cpp.html
## Касаи за O(n) для подсчёта LCP

<br>
# Задачи на суффмассив
## Число различных подстрок
## Поиск общей подстроки k строк
## LZSS (архиватор)
## Поиск подстроки в тексте за O(|s| + log|text|)
### Собственно алгоритм: SM &ge; max(min(SL, ML), min(SR, MR))
### Вычисление ML и MR за O(1) с предподсчётом за O(n): дерево отрезков
### Доказательство того, что при SM++ увеличится на следующей фазе max(SL, SR)

<br>
# Задачи на тему Ахо-Корасик (в конце, т.к. имеет меньший приоритет)
## Поиск подстроки в боре
## Посчитать для каждого словарного слова, сколько раз оно встречается в тексте, найти самое левое и самое правое вхождения
## Разбить строку длины 10^5 на словарные слова суммарной длины 10^5.
