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

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

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

Описание

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