Лекция 10. Суффиксный массив

Среда, 15 апреля 2020

Онлайн, занятие в zoom

Описание

Cуффиксный массив
- Определение суффиксного массива
- Алгоритм удвоения префикса для построения за $\mathcal{O}(n \log^2(n))$
- Использование цифровой сортировки для построения за $\mathcal{O}(n \log{n})$
- Нахождение LCP суффиксов, используя суффиксный массив
- Построение массива LCP соседних в суффиксном массиве суффиксов за $\mathcal{O}(n)$ (Касаи, Ли, Аримура, Арикава, Пак)