Разбор теоретического задания 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|)$, можно воспользоваться микро-макро-оптимизацией.