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