Применение равномерно разреженных суффиксных деревьев для задач обработки строк

Аннотация

Потребность в эффективных алгоритмах обработки строк возникает во многих практических задачах. Одним из наиболее универсальных подходов является применение суффиксных деревьев. Однако, данная структура имеет высокие требования к памяти, что ограничивает область её применения. В данной статье на примере задачи о максимальной симметричной подстроке рассматривается способ, позволяющий частично устранить данный недостаток. Описанный способ может быть использован и для других задач.

Abstract

The need for efficient algorithms for processing strings arises in many practical problems. One of the most universal approaches is the use of suffix trees. However, this data structure has high memory requirements, which limits area of its application. In this article we consider a way to partially eliminate this disadvantage and give an example of solving the problem of the longest symmetric substring. The described method can be also be used for other problems too.