Суффиксный массив. Параллель B'. 24.04.2021

00:00:00 - Начало, определение и пример суффиксного массива 00:19:07 - Сортировка циклических сдвигов по префиксам длины 2^k 00:21:52 - Первый этап, k = 0 00:27:17 - Переход k - 1 в k 00:30:17 - Ранг суффикса, массив rank 00:38:42 - Классы эквивалентности, массив c 00:45:57 - Сравнение префиксов длины 2^k с помощью массивов suf, rank и c 00:56:37 - Сортировка на k-ом шаге 01:01:27 - Уменьшаем в 2 раза число сортировок 01:08:47 - Stable Count Sort 01:18:16 - Ещё раз кратко о всём алгоритме 01:24:18 - Асимптотика алгоритма 01:26:23 - LCP, пример 01:29:33 - LCP любых двух суффиксов, SparseTable на массиве lcp 01:39:13 - Алгоритм Аримуры-Арикавы-Касаи-Ли-Парка 01:53:43 - Подсчёт числа различных подстрок за O(nlogn)