Optimal Suffix Tree Construction with Large Alphabets
Author: Martin Farach
ABSTRACT
The suffix tree of a string is the fundamental data structure of
combinatorial pattern matching. In this paper, we present a novel,
deterministic algorithm for the construction of suffix trees.
We settle the main open problem in the construction of suffix trees:
we build suffix trees in linear time for integer alphabet.
DIMACS Home Page