What is a suffix array?

AlgorithmsJunior~4 min read

Short answer

A suffix array (SA) is an array of the indices of all of a string's suffixes, sorted in lexicographic order. It enables efficient substring search (via binary search), computing the LCP array, counting distinct substrings, finding the longest repeated substring, and it is used in data compression (for example, BWT). It is built in O(n log n) (or O(n) with advanced algorithms), and substring search is O(m log n).

Detailed explanation

What it is and why it is needed

Let S be a string of length n. Consider all its suffixes S[i..n-1]. If we sort these suffixes lexicographically and keep only their starting positions, we get the suffix array SA. With SA, you can perform a fast search for a pattern P in S using binary search over the sorted suffixes, and solve many string problems more efficiently than with naive methods.

Formal definition

The string S[0..n-1] usually gets a unique minimal sentinel character appended, for example '$', which does not appear in S's alphabet and is lexicographically smaller than any other character. This simplifies boundary cases.
The suffix array SA is a permutation of the indices [0..n-1] such that the suffixes S[SA[0]..], S[SA[1]..], ..., S[SA[n-1]..] are ordered lexicographically, non-decreasing.
The LCP array (Longest Common Prefix) complements SA: LCP[i] is the length of the longest common prefix between the suffixes at indices SA[i] and SA[i-1] (for i=0 it is usually 0). It can be built in O(n) from S and SA (Kasai's algorithm).

Example: "banana$"

Consider the string S = "banana$" (indices 0..6). The list of suffixes and their sort order:

Indices and suffixes:
banana$
anana$
nana$
ana$
na$
a$
$

Sorted suffixes (lexicographically):
$
a$
ana$
anana$
banana$
na$
nana$

SA = [6, 5, 3, 1, 0, 4, 2]
LCP = [0, 0, 1, 3, 0, 0, 2]

Here LCP[3] = 3, because ana$ and anana$ share the prefix "ana" of length 3; the maximum LCP is 3, so the longest repeated substring in "banana" has length 3 ("ana").

Applications

Fast search for a substring P in S: binary search over SA in O(m log n), where m is the length of P.
Counting the number of distinct substrings: n(n+1)/2 − sum(LCP).
Finding the longest repeated substring: max(LCP).
Data compression and indexing: the reversible Burrows-Wheeler transform (BWT) is built on top of SA.

Construction algorithms (idea and complexity)

Naive: sort all the suffixes as strings, O(n^2 log n) time, O(n) memory, often too slow.
Prefix-doubling: sort pairs of ranks (k and a k-shift), doubling k: O(n log n) sorts; in practice often O(n log n). Simple to implement.
DC3/Skew, SA-IS: linear time O(n), harder to implement, used in production libraries.
LCP (Kasai's algorithm): O(n) given an already-built SA.

Searching for a substring via a suffix array

Build SA for S (and, optionally, LCP).
Run a binary search over the suffix array, comparing P against the suffix S[SA[mid]..].
Find the range [lo..hi) of suffixes that start with P. That is every occurrence of P in S.

// Building a suffix array (prefix-doubling) and the LCP array (Kasai's algorithm)
// Important: append a unique minimal character to the string, for example '$', which does not appear in the original string.

function buildSuffixArray(s) {
  const n = s.length;
  const sa = Array.from({ length: n }, (_, i) => i);
  // Ranks by character (use code points; for ASCII/UTF-16, codePointAt is enough)
  let rank = Array.from(s, ch => ch.codePointAt(0));
  let tmp = new Array(n).fill(0);

  for (let k = 1; k < n; k <<= 1) {
    sa.sort((i, j) => {
      if (rank[i] !== rank[j]) return rank[i] - rank[j];
      const ri = i + k < n ? rank[i + k] : -1;
      const rj = j + k < n ? rank[j + k] : -1;
      return ri - rj;
    });

    tmp[sa[0]] = 0;
    for (let i = 1; i < n; i++) {
      const a = sa[i - 1];
      const b = sa[i];
      const same = rank[a] === rank[b]
        && (a + k < n ? rank[a + k] : -1) === (b + k < n ? rank[b + k] : -1);
      tmp[b] = tmp[a] + (same ? 0 : 1);
    }
    for (let i = 0; i < n; i++) rank[i] = tmp[i];
    if (rank[sa[n - 1]] === n - 1) break; // every rank is unique
  }
  return sa;
}

function buildLCP(s, sa) {
  const n = s.length;
  const rank = new Array(n);
  for (let i = 0; i < n; i++) rank[sa[i]] = i;
  const lcp = new Array(n).fill(0);
  let k = 0;
  for (let i = 0; i < n; i++) {
    const r = rank[i];
    if (r === 0) { k = 0; continue; }
    const j = sa[r - 1];
    while (i + k < n && j + k < n && s[i + k] === s[j + k]) k++;
    lcp[r] = k;
    if (k > 0) k--;
  }
  return lcp;
}

// Binary search for a substring P in S over SA
function findOccurrences(s, sa, pat) {
  const n = s.length;
  const m = pat.length;

  const cmpLower = (idx) => {
    // compare the first m characters
    const sub = s.slice(idx, idx + m);
    if (sub === pat) return 0;
    return sub < pat ? -1 : 1; // lexicographic comparison of JS strings
  };

  // lower bound (the first place where the suffix >= the pat prefix)
  let lo = 0, hi = n;
  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    const c = cmpLower(sa[mid]);
    if (c >= 0) hi = mid; else lo = mid + 1;
  }
  const start = lo;

  // upper bound (the first place where the suffix > the pat prefix)
  const cmpUpper = (idx) => {
    const sub = s.slice(idx, idx + m);
    return sub <= pat ? -1 : 1;
  };
  lo = 0; hi = n;
  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    const c = cmpUpper(sa[mid]);
    if (c <= 0) lo = mid + 1; else hi = mid;
  }
  const end = lo;

  const res = [];
  for (let i = start; i < end; i++) res.push(sa[i]);
  // It is often convenient to return the indices sorted by occurrence position
  return res.sort((a, b) => a - b);
}

// Demonstration
const s = "banana$"; // '$' does not occur in the string and is minimal
const sa = buildSuffixArray(s);
const lcp = buildLCP(s, sa);
console.log("SA:", sa);           // [6, 5, 3, 1, 0, 4, 2]
console.log("LCP:", lcp);         // [0, 0, 1, 3, 0, 0, 2]
console.log(findOccurrences(s, sa, "ana")); // [1, 3]

Relation to the suffix tree

The suffix tree is a more powerful structure with a larger constant memory factor (often ~O(n), but with a larger coefficient).
The suffix array is more compact, easier to store and serialize; with LCP and an RMQ it can emulate many of a tree's operations.

Common problems and formulas

The number of distinct substrings of a string S of length n: n(n+1)/2 − Σ LCP[i]. Intuition: there are n(n+1)/2 substrings in total, and the shared prefixes between neighboring suffixes in SA "duplicate" substrings and are subtracted via the sum of LCP.
The longest repeated substring: take the index i with the maximum LCP[i]; the answer is S[SA[i] .. SA[i] + LCP[i] - 1].
The number of occurrences of a pattern P: the size of the range [lower_bound(P), upper_bound(P)) over SA.

Pitfalls and tips

Always append a unique minimal sentinel (for example, '$') to correctly handle suffixes, avoid ambiguity, and simplify comparisons at the string's boundary.
Watch the lexicographic order in your chosen encoding. In JS, string comparison is lexicographic over UTF-16 code units; Unicode peculiarities may need normalization.
Prefix-doubling is easy to implement and fast enough in practice. For very large data, use SA-IS/DC3.

Complexity (summary)

Building SA: O(n log n) (prefix-doubling) or O(n) (SA-IS/DC3). Memory: O(n).
Building LCP (Kasai's algorithm): O(n) given SA.
Searching for a substring P: O(m log n) with binary search; with LCP and an RMQ, individual comparisons can be sped up.

Short Answer

Interview ready

Premium

A concise answer to help you respond confidently on this topic during an interview.