2024
2023
2022
2021
2020
2019
2018
2017
Препроцессинг текста, суффиксные деревья, суффиксные массивы. Сложность текста, сжатие
1. (0.5)Написать программу, которая строит суффиксный массив текста и позволяет искать в нем паттерны. Продемонстрировать ее работу (Пример: текст ababcabca, осуществить поиск слова bcab).
2. (1.5)Написать программу, которая строит суффиксное дерево для текста и позволяет искать в нем паттерны. Продемонстрировать ее работу (Пример: осуществить поиск слова bca в тексте ababcabca).
3. (0.3)Оцените сложность текста «aababbabaaba» в системе описания допускающей порождение символов и копирование части текста (начиная с позиции "i" копируем кусок длины "l").
4. (0.3)Оцените сложность текста «aababbabaaba» в системе описания допускающей порождение заданного количества символов.