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

Задача 1

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

б) Михаил Слабодкин

в) Ольга Самойлова

г) Денис Рахманкин

Задача 2

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

Задача 3

Михаил Слабодкин

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

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

1. а) Как за линейное время построить из суффиксного дерева суффиксный массив?

   б) Как за линейное время построить из суффиксного массива сжатое суффиксное дерево [без суффиксных ссылок и функции перехода]?

2. Дана строка \(s\). Постройте за время \(\mathcal O(|s|)\) структуру данных, за \(\mathcal O(\log n)\) отвечающую на запрос \(\mathrm{occurences}(\ell,r)\): сколько раз \(s[\ell..r]\) входит как подстрока в \(s\)?

   • На семинаре мы дошли до времени и памяти \(\mathcal O(|s|\log|s|)\) на предподсчёт и \(\mathcal O(\log|s|)\) на запрос. Чтобы ускорить предподсчёт до \(\mathcal O(|s|)\), можно воспользоваться микро-макро-оптимизацией.