City: Test Saint Petersburg Novosibirsk Kazan Language: Русский English

Семинар 3. Суффиксный массив
Advanced chapters of algorithms, part 2

What: Seminar
When: Monday, 21 February 2022, 20:00–21:30
Where: Онлайн, занятие в zoom

Description

Разбор теоретического задания 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\) в качестве подстроки.

Video