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

Семинар 4. Суффиксное дерево
Advanced chapters of algorithms, part 2

What: Seminar
When: Tuesday, 01 March 2022, 00:00–01:30
Where: Онлайн, занятие в zoom

Description

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