Application of Evenly Sparse Suffix Tree for String Processing Tasks

S. F. Svinyin^a, I. A. Andrianov<sup>b

a</sup> St. Petersburg Institute for Informatics and Automation of RAS
^b Vologda State University

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.

Keywords: Information Retrieval, Sparse Suffix Trees, Least Common Ancestor, Maximal Palindrome, Ukkonen's Algorithm.

UDC: 681.3.07