The time complexity of suffix tree construction has been shown to be equivalent to that of sorting:
O(
n) for a constant-size alphabet or an integer alphabet and
O(
n log
n) for a general alphabet. However, previous algorithms for constructing suffix arrays have the time complexity of
O(
n log
n) even for a constant-size alphabet.
In this paper we present a linear-time algorithm to construct suffix arrays for integer alphabets, which do not use suffix
trees as intermediate data structures during its construction. Since the case of a constant-size alphabet can be subsumed
in that of an integer alphabet, our result implies that the time complexity of directly constructing suffix arrays matches
that of constructing suffix trees.
Supported by KOSEF grant R01-2002-000-00589-0.
Supported by BK21 Project and IMT2000 Project AB02.