Строки: суффиксный массив (21 октября 2024)

1. [5 минут] Решение суфф массивом задач
   1. Напоминание, что суффмассив весит O(n) и мы его умеем строить в лоб за O(n²logn) и хешами за O(nlog²n)
   2. Поиск подстроки в тексте за O(|s|log|T|) и O(|s|+log|s|log|T|)
   
   
2. [35 минут] Суффиксный массив за O(nlogn)
   1. Сортируем циклические сдвиги строки s#
   2. За O(Σ + n²) цифровой сортировкой
   3. От k переходим не к k+1, а к 2k, внутри используем сортировку подсчётом для пар, уже отсортированных по второй половине
   4. Учимся писать, должно получиться что-то типа моего
   
   
3. [10 минут] Алгоритм Касаи LCP за O(n)

1. [15 минут] Алгоритм поиска подстроки в тексте за O(|s| + log|T|)
   1. Собственно алгоритм: SM ≥ max(min(SL, ML), min(SR, MR))
   2. Вычисление ML и MR за O(1) с предподсчётом за O(n): дерево отрезков
   3. Доказательство того, что при SM++ увеличится на следующей фазе max(SL, SR)
   
   
2. Бор, суфдерево
   1. Основа. Пример хранение int next[N][26]
   2. Применения: unordered_set, set, сортировка строк.
   3. Хранение для применений выше
   4. Суф.дерево, поиск строки в тексте
   5. Сжатое суфдерево, сжатый бор

1. [25 минут] Доп лекция. Суффиксный массив за O(n). Алгоритм Каркайнена-Сандерса.
   1. Условие входа в функцию: дана строка длины n над алфавитом не более 2n.
   2. Новый алфавит − тройка подряд идущих символов. За O(n) цифровой сортировкой получили номера символов.
   3. SA(s): SA(s₀s₁) + Sort(s₂) + Merge(s₀s₁, s₂).
   4. Оценки времени: T(n) = O(n) + T(2n/3) + O(n) + O(n) = O(n).