Suffix Array

Suffix array is a space-efficient full-text index data structure within computation and algorithms that stores the starting indices of all n suffixes of a string T[0..n − 1] arranged in lexicographical order. Introduced in 1990 by Udi Manber and Gene Myers (and independently described as the PAT array by Gaston Gonnet, Ricardo Baeza-Yates, and Tim Snider at the University of Waterloo for indexing the Oxford English Dictionary), the suffix array was designed to match the substring-query capabilities of a suffix tree (a path-compressed trie of all suffixes) while reducing memory consumption by a factor of 3 to 5—from 16–20*n* bytes of tree pointers down to a single contiguous array of n integers (4n bytes for 32-bit indices).

Because every occurrence of a query pattern P[0..m − 1] inside T is the prefix of some suffix of T, all occurrences of P occupy a single contiguous interval [L, R] inside the suffix array SA[0..n − 1]. Binary search over SA locates this interval in O(m log n) time using SA alone, or in O(m + log n) time when augmented with the Longest Common Prefix (LCP) array (Manber & Myers, 1990) and a range minimum query (segment tree or Cartesian tree) structure—reaching optimal O(m + occ) time in Abouelhoda, Kurtz, and Ohlebusch's Enhanced Suffix Array (ESA, 2004). Within computational complexity theory and modern genomics, suffix arrays can be constructed in linear O(n) time and serve as the mathematical bridge to the Burrows–Wheeler transform (BWT) and FM-index powering whole-genome read aligners (STAR, Bowtie2, BWA-MEM).

Lexicographical Suffix Permutation SA[0..n−1]

Let T = T[0..n − 1] be a string of length n over an ordered alphabet Σ, terminated at T[n − 1] = § by a sentinel § smaller than every other character in Σ. For each i ∈ {0, ..., n − 1}, let S_i = T[i..n − 1] denote the i-th suffix. The suffix array SA[0..n − 1] is the unique permutation of {0, ..., n − 1} sorting all suffixes lexicographically:

Here SA[0] = n − 1 always holds because S_n−1 = "§" is smallest, and the inverse suffix array ISA[SA[r]] = r maps each text position i to its sorted rank r. On the benchmark string T = "BANANA§" (n = 7, § < A < B < N), the sorted suffixes § (S₆), A§ (S₅), ANA§ (S₃), ANANA§ (S₁), BANANA§ (S₀), NA§ (S₄), NANA§ (S₂) yield SA = [6, 5, 3, 1, 0, 4, 2].

The LCP Array and Kasai's Linear-Time O(n) Construction

The Longest Common Prefix (LCP) array LCP[0..n − 1] stores the shared prefix length of adjacent sorted suffixes: LCP[0] = 0 and LCP[r] = lcp(S_SA[r−1], S_SA[r]) (yielding LCP = [0, 0, 1, 3, 0, 0, 2] for "BANANA§"). For arbitrary ranks i < j, lcp(S_SA[i], S_SA[j]) = min_i<k≤j LCP[k]. Kasai's algorithm (Kasai et al., 2001) constructs LCP[0..n − 1] in linear O(n) time by scanning in text order i = 0..n − 1 and using LCP[ISA[i]] ≥ LCP[ISA[i − 1]] − 1, so the matched length h decrements at most n times and increments at most 2n times.

Prefix Doubling vs. Divide-and-Conquer DC3 and Induced Sorting (SA-IS)

Manber and Myers (1990) constructed suffix arrays in O(n log n) time using prefix doubling (Karp–Miller–Rosenberg naming): in stage k = 0, 1, ..., ⌈log₂ n⌉, suffixes are sorted by their prefixes of length 2^k using the 2^k−1-length integer ranks of S_i and S_i+2^k−1 as a two-word radix key.

In 2003, Kärkkäinen & Sanders (DC3 / Skew), Ko & Aluru, and Kim et al. independently proved that suffix arrays can be constructed directly in worst-case linear O(n) time without building a suffix tree. Subsequently, Nong, Zhang, and Chan (2009) introduced SA-IS (Suffix Array by Induced Sorting), which classifies every suffix S_i as S-type (S_i <_lex S_i+1) or L-type (S_i >_lex S_i+1), recursively sorts only the LMS (Leftmost S-type) substrings, and induces the sorted order of all L-type and S-type suffixes in two linear bucket scans.

Algebraic Equivalence to the Burrows–Wheeler Transform (BWT)

The suffix array SA[0..n − 1] is directly equivalent to the Burrows–Wheeler transform string BWT[0..n − 1]: the r-th character of the BWT is the character preceding suffix SA[r] in the cyclic text T:

Ferragina and Manzini's FM-index (2000) stores the wavelet-tree-compressed BWT alongside a sparse sample of SA, shrinking the full-text index of the 3.1-gigabase human genome from ~12.4 GB to under 1.5 GB while preserving backward substring search.

In transcriptomics, STAR (Spliced Transcripts Alignment to a Reference, Dobin et al., 2013) maintains an Enhanced Suffix Array in RAM to compute Maximal Mappable Prefixes (MMP) of spliced RNA-seq reads across exon–exon junctions. In whole-genome alignment (MUMmer4), generalized suffix arrays find all Maximal Unique Matches (MUMs) and Maximal Exact Matches (MEMs) between chromosomes in linear O(n₁ + n₂) time by merging LCP intervals via a disjoint-set data structure or bottom-up stack.

How does an Enhanced Suffix Array (ESA) replace a suffix tree in linear time?

Every internal node u of a suffix tree corresponds to an ℓ-interval [i..j] in the suffix array where LCP[i] < ℓ, LCP[j + 1] < ℓ, and min_i<k≤j LCP[k] = ℓ. Augmenting SA and LCP with a child-interval table allows every top-down, bottom-up, and suffix-link traversal on a suffix tree to execute on the Enhanced Suffix Array in identical O(n) or O(m) time with smaller memory footprint.

Why is a unique sentinel symbol § appended to the string before building a suffix array?

Without a unique sentinel § smaller than every alphabet symbol, a shorter suffix S_i that is a prefix of a longer suffix S_j (such as "ANA" vs. "ANANA" in "BANANA") has no differing character at which to break ties cleanly, violating the suffix-tree leaf bijection.

1. Manber, U., & Myers, G. (1993). "Suffix arrays: A new method for on-line string searches." SIAM Journal on Computing, 22(5), 935–948. https://doi.org/10.1137/0222058
2. Kasai, T., Lee, G., Arimura, H., Arikawa, S., & Park, K. (2001). "Linear-time longest-common-prefix computation in suffix arrays and its applications." Proceedings of the 12th Annual Symposium on Combinatorial Pattern Matching (CPM), LNCS 2089, 181–192. https://doi.org/10.1007/3-540-48194-X_17
3. Abouelhoda, M. I., Kurtz, S., & Ohlebusch, E. (2004). "Replacing suffix trees with enhanced suffix arrays." Journal of Discrete Algorithms, 2(1), 53–86. https://doi.org/10.1016/S1570-8667(03)00065-000065-0)
4. Kärkkäinen, J., Sanders, P., & Burkhardt, S. (2006). "Linear work suffix array construction." Journal of the ACM, 53(6), 918–936. https://doi.org/10.1145/1217856.1217858
5. Nong, G., Zhang, S., & Chan, W. H. (2011). "Two efficient algorithms for linear time suffix array construction." IEEE Transactions on Computers, 60(10), 1471–1484. https://doi.org/10.1109/TC.2010.188