Город: Санкт-Петербург Новосибирск Казань Язык: Русский English

Семинар 3. Суффиксный массив
Дополнительные главы алгоритмов, часть 2

Что: Семинар
Когда: Вторник, 22 февраля 2022, 00:00–01:30
Где: Онлайн, занятие в zoom

Описание

Разбор теоретического задания 1

Задача 2

Денис Рахманкин, Михаил Слабодкин

Задача 3

а) Сергей Холодилов

б) Сергей Холодилов

в) Ольга Самойлова, Денис Рахманкин

Задача 4

Арина Уланова, Ольга Самойлова

Задачи с семинара 3

Полагаем \(|\Sigma|=\mathcal O(1)\).

  1. Дана строка \(t\). Постройте за время \(\mathcal O(|t|\log|t|)\) структуру данных, позволяющую за время \(\mathcal O(|s|+\log|t|)\) отвечать на online-запросы \(\mathrm{occurences}(s)\): по строке \(s\) найти число вхождений \(s\) в \(t\) в качестве подстроки.

Видео