The Prague Stringology Conference 2002

Shunsuke Inenaga

Bidirectional Construction of Suffix Trees

Abstract:
String matching is critical in information retrieval since in many cases information is stored and manipulated as strings. Constructing and utilizing suitable data structures for text strings, we can solve the string matching problem efficiently. Such structures are called index structures. The suffix tree is certainly the most widely-known and extensively-studied structure of this kind. In this paper, we present a linear-time algorithm for bidirectional construction of suffix trees.

Download paper: Article in PostScript Article in PDF
 PostScript   PDF