1993/10/01 by Udi Manber, Gene Myers · 1,965 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Algorithm #Algorithms and Data Compression #Arithmetic #Combinatorics #Compressed suffix array #Computer science #DNA and Biological Computing #Data structure #Generalized suffix tree #Genomics and Phylogenetic Studies #Mathematics #String (physics) #String searching algorithm #Substring #Suffix #Suffix array #Suffix tree #Time complexity #sort
paper · doi:10.1137/0222058
published in SIAM Journal on Computing 22(5), 935-948 (Society for Industrial and Applied Mathematics)
openalex publication_date 1993/10/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/31
A new and conceptually simple data structure, called a suffix array, for on-line string searches is introduced in this paper. Constructing and querying suffix arrays is reduced to a sort and search paradigm that employs novel algorithms. The main advantage of suffix arrays over suffix trees is that, in practice, they use three to five times less space. From a complexity standpoint, suffix arrays permit on-line string searches of the type, “Is W a substring of A?” to be answered in time O(P + log N), where P is the length of W and N is the length of A, which is competitive with (and in some cases slightly better than) suffix trees. The only drawback is that in those instances where the underlying alphabet is finite and small, suffix trees can be constructed in O(N) time in the worst case, versus O(Nlog N) time for suffix arrays. However, an augmented algorithm is given that, regardless of the alphabet size, constructs suffix arrays in O(N)expected time, albeit with lesser space efficiency. It is believed that suffix arrays will prove to be better in practice than suffix trees for many applications.