Kodomo

Пользователь

Учебная страница курса биоинформатики,
год поступления 2015

Препроцессинг текста, суффиксные деревья, суффиксные массивы. Сложность текста, сжатие

1. (0.5)Написать программу, которая строит суффиксный массив текста и позволяет искать в нем паттерны. Продемонстрировать ее работу (Пример: текст ababcabca, осуществить поиск слова bcab).

2. (1.5)Написать программу, которая строит суффиксное дерево для текста и позволяет искать в нем паттерны. Продемонстрировать ее работу (Пример: осуществить поиск слова bca в тексте ababcabca).

3. (0.3)Оцените сложность текста «aababbabaaba» в системе описания допускающей порождение символов и копирование части текста (начиная с позиции "i" копируем кусок длины "l").

4. (0.3)Оцените сложность текста «aababbabaaba» в системе описания допускающей порождение заданного количества символов.