все очень прилично!
Информация о работе
Подробнее о работе
Дисциплина: Алгоритмы и структуры данных Задание: Поиск наибольшей общей подстроки с помощью суффиксного дерева.
- 18 страниц
- 2021 год
- 6 просмотров
- 0 покупок
Гарантия сервиса Автор24
Уникальность не ниже 50%
Фрагменты работ
Задание.
Поиск наибольшей общей подстроки с помощью суффиксного дерева.
1. Теоретическая часть.
1.1. Формальные понятия и определения.
Последовательность символов (возможно, пустая) из алфавита обозначается буквами r, s и t и называется строкой. |t| обозначает длину строки t.
Префикс r строки t — строка такая, что rs = t для некоторой (возможно, пустой) строки s.
Суффикс r строки t — строка такая, что sr = t для некоторой (возможно, пустой) строки s.
Суффиксное дерево – это нагруженное дерево, содержащее все суффиксы некоторой строки[1].
Нагруженное дерево – структура данных, представляет собой корневое дерево, у которого для любого узла все рёбра, соединяющие этот узел с его сыновьями, помечены разными символами. Некоторые узлы префиксного дерева выделены. Считается, что префиксное дерево содержит данную строку-ключ тогда и только тогда, когда эту строку можно прочитать на пути из корня до некоторого (единственного для этой строки) выделенного узла. В некоторых приложениях удобно считать все узлы дерева выделенными[3].
Таким образом, ключ, идентифицирующий конкретный узел дерева, не явно хранится в данном узле, а задаётся положением данного узла в дереве. Получить ключ можно выписыванием подряд символов, помечающих рёбра на пути от корня до узла. Ключ корня дерева — пустая строка. Часто в выделенных узлах хранят дополнительную информацию, связанную с ключом, и обычно выделенными являются только листья и, возможно, некоторые внутренние узлы[3].
• Алгоритмы обработки данных: учебное пособие / В.В. Ландовский. – Новосибирск: Изд-во НГТУ, 2018. – 67 с.
• Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ, 3-е издание –
М.: «Вильямс», 2013. – 1328 с.
• https://en.wikipedia.org/wiki/Suffix_tree
Форма заказа новой работы
Не подошла эта работа?
Закажи новую работу, сделанную по твоим требованиям
