В 2022 году Computer Science Center приостановил набор и обучение
Направления
Курсы
Онлайн-образование
Поступление
О центре
Войти
Направления
Курсы
Онлайн-образование
Онлайн-курсы
Онлайн-программы
Видеозаписи лекций
Поступление
Подать заявку
Памятка
Программа для поступления
Вопросы и ответы
О центре
Преподаватели
Выпускники
Отзывы
Команда
История
Курсы
/
Алгоритмы и структуры данных, часть 2
/
весна 2020
/
Лекция 10. Суффиксный массив
Среда, 15 апреля 2020
Онлайн, занятие в zoom
Описание
Cуффиксный массив
Определение суффиксного массива
Алгоритм удвоения префикса для построения за \(\mathcal{O}(n \log^2(n))\)
Использование цифровой сортировки для построения за \(\mathcal{O}(n \log{n})\)
Нахождение LCP суффиксов, используя суффиксный массив
Построение массива LCP соседних в суффиксном массиве суффиксов за \(\mathcal{O}(n)\) (Касаи, Ли, Аримура, Арикава, Пак)