ИСПОЛЬЗОВАНИЕ РАЗРЕЖЕННЫХ СУФФИКСНЫХ ДЕРЕВЬЕВ ДЛЯ ЗАДАЧ ОБРАБОТКИ ТЕКСТОВ
Потребность в эффективных алгоритмах обработки строк возникает во многих практических задачах. Одной из классических задач в этой области является задача поиска наибольшей общей подстроки. Для ее решения предлагается использовать разреженные суффиксные деревья, приводится описание алгоритма. Такой подход позволит обрабатывать данные существенно большего размера, чем в случае использования обычных суффиксных деревьев. Также в статье рассматривается решение задачи поиска максимальной симметричной подстроки.
Авторы: А. Р. Лисс, И. А. Андрианов
Направление: Информатика, управление и компьютерные технологии
Ключевые слова: Разреженные суффиксные деревья, поиск по сходству, алгоритм Укконена
Открыть полный текст статьи