96-48: Optimal Suffix Tree Construction with Large Alphabets

DIMACS TR: 96-48

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.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-48.ps.gz

DIMACS Home Page