alexey-sagaydak/alg-rgz

Наивный on-line алгоритм построения суффиксного дерева за O(n^3). Проведение анализа алгоритма

Расчетно-графическая работа по дисциплине "Алгоритмы и структуры данных"

Описание

Наивный on-line алгоритм построения суффиксного дерева за O(n^3).

Задание

1. Провести анализ алгоритма в соответствии с вариантом.
2. Разработать или доработать программную реализацию алгоритмов для оценки времени их работы.
3. Если алгоритм нуждается в дополнительной памяти, объем которой зависит от входных данных, проанализировать затраты памяти.
4. Построить экспериментальные зависимости затраченного времени и, при необходимости, памяти от объема входных (или хранимых) данных.
5. Обосновать наличие или отсутствие различных вариантов входного потока («хороших» и «плохих»), если различия существуют, дать оценку в лучшем и в худшем случае.
6. Сравнить полученные результаты с теоретическими оценками.

Содержание отчета

1. Задание.

2. Теоретическая часть.

   2.1 Подробное описание алгоритма (псевдокод/диаграммы, схемы структур данных).

   2.2 Обоснование теоретических оценок временной сложности.

3. Экспериментальная часть.

   3.1 Контрольные примеры (для демонстрации корректности реализации).

   3.2 Результаты экспериментов (таблицы, графики, примеры тестовых данных).

   3.3. Выводы.

4. Тексты программ.

5. Список использованных источников и литературы.

Пример работы программы

Входные данные: Novosibirsk

Выходные данные:

Total time: 377 (microseconds)
+
+-- Novosibirsk
+-+ o
| +-- vosibirsk
| +-- sibirsk
+-- vosibirsk
+-+ s
| +-- ibirsk
| +-- k
+-+ i
| +-- birsk
| +-- rsk
+-- birsk
+-- rsk
+-- k