День 5. Строки: суффиксный массив

1. Построение суффиксного массива
1. Определение суффиксного массива (сортированный массив циклических сдвигов). Хранение в памяти: O(n).
2. Сравнение строк хешами на больше-меньше и построение суффиксного массива за O(nlog²n)
3. Построение суффиксного массива цифровой сортировкой за O(n²)
4. Построение суффиксного массива цифровой сортировкой с удвоением за O(nlogn)
5. Суффиксы ⇔ циклические сдвиги


2. LCP
1. Определение, полный предподсчёт за O(n²)
2. Вычисление хешами LCP(i, j) за O(logn)
3. Вычисление LCP всех соседних за O(n): алгоритм Касаи
4. Вычисление LCP произвольных за O(1): RMQ за O(1)


3. Задачи
1. Поиск подстроки в тексте. Предподсчёт от текста. Ответ на запрос за O(|s|log|T|)
2. А теперь O(|s| + log|s|log|T|) и даже за O(|s| + log|T|)
3. Количество вхождений строки
4. Количество различных подстрок
5. Общая подстрока 2 строк (k строк).