Суффиксный массив
- [Сережа.K] С/C++
- Конструкторы и деструкторы
- Finalize через деструкторы
- public, private, struct, class, наследование
- свой модный вектор с unique!
- nth_element: стандартный метод, реализация через qsort за O(n)
- [Сережа.М] Суффиксный зоопарк
- Суффиксный массив за O(nlog2n) хешами
- Суффиксный массив за O(nlogn)
- Сортировка подсчетом
- Цифровая сортировка
- Суффиксы → циклические сдвиги
- Основная фаза: удвоение длины
- LCP
- Алгоритм Касаи для подсчета LCP за O(n)
- Проблемы в случае циклических сдвигов и периодичной строки
- Задачи на строки, решение деревом и массивом
- LCP любых двух за O(1): RMQ в массиве, LCA в дереве
- Поиск строки в тексте (строим структуру от текста, отвечаем на запрос-строку)
- Число различных подстрок
- Общая подстрока двух строк
- Общая подстрока k строк
- [skipped] Число подпалиндромов
- [skipped] Число общих подпалиндромов
- [skipped] k-я лексикографически общая подстрока
- [skipped] Найти самую длинную строку, которая встречается как подстрока хотя бы k раз