Наивный on-line алгоритм построения суффиксного дерева за O(n^3)
.
- Провести анализ алгоритма в соответствии с вариантом.
- Разработать или доработать программную реализацию алгоритмов для оценки времени их работы.
- Если алгоритм нуждается в дополнительной памяти, объем которой зависит от входных данных, проанализировать затраты памяти.
- Построить экспериментальные зависимости затраченного времени и, при необходимости, памяти от объема входных (или хранимых) данных.
- Обосновать наличие или отсутствие различных вариантов входного потока («хороших» и «плохих»), если различия существуют, дать оценку в лучшем и в худшем случае.
- Сравнить полученные результаты с теоретическими оценками.
-
Задание.
-
Теоретическая часть.
2.1 Подробное описание алгоритма (псевдокод/диаграммы, схемы структур данных).
2.2 Обоснование теоретических оценок временной сложности.
-
Экспериментальная часть.
3.1 Контрольные примеры (для демонстрации корректности реализации).
3.2 Результаты экспериментов (таблицы, графики, примеры тестовых данных).
3.3. Выводы.
-
Тексты программ.
-
Список использованных источников и литературы.
Входные данные: Novosibirsk
Выходные данные:
Total time: 377 (microseconds)
+
+-- Novosibirsk
+-+ o
| +-- vosibirsk
| +-- sibirsk
+-- vosibirsk
+-+ s
| +-- ibirsk
| +-- k
+-+ i
| +-- birsk
| +-- rsk
+-- birsk
+-- rsk
+-- k