Construction of Suffix Trees in Linear Time
Leung Yiu Cho
Department of Computer Science
HKUST

September 26, 2003
11-11:50 AM
Room 3501, HKUST


Abstract:
Given a string P and a longer string T, the exact matching problem is
to find all occurences, if any, of P in T. The Suffix Tree is a data
structure which can be used to solve the exact problem in linear time.
Given a string T of length m, the algorithm takes O(m) time to construct
the suffix tree. After this preprocessing stage, for any string P of length
n, the number of ocurrences of P in T can be found in O(n+k)-time,
where k is the number of ocurrences of P in T.
Weiner gave the first linear-time construction algorithm
for suffix trees in 1973. McCreight gave another linear-time aglorithm
which is more space efficient a few years later. In Ukkonen [1] gave a
simpler linear-time algorithm. The algorithm
explained in this seminar will be based on Ukkonen's algorithm.

[1] E. Ukkonen. On-line construction of suffix-trees.
Algorithmica, 14:249-60, 1995.