DIMACS TR: 96-48
Optimal Suffix Tree Construction with Large Alphabets
Author: Martin Farach
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.
Paper Available at:
DIMACS Home Page