Suffix Array Construction — O(n log n) Sorting and the Kasai LCP Algorithm

Algorithm Statement#

The suffix array SA of a string s of length n is the permutation of [0, n) such that s[SA[0]..], s[SA[1]..], ..., s[SA[n-1]..] are the suffixes of s sorted lexicographically. The Kasai algorithm augments the suffix array with the longest common prefix array LCP[i], defined as the length of the longest common prefix of s[SA[i]..] and s[SA[i-1]..].

Several construction algorithms exist:

• Naive sort: O(n^2 log n) using direct suffix comparisons.
• Prefix doubling (Manber-Myers): O(n log^2 n) with simple sort, O(n log n) with radix sort.
• DC3 / SA-IS: O(n) but complex to implement.

Time: O(n log n) for prefix doubling, O(n) for Kasai LCP given the suffix array. Space: O(n).

Why This Algorithm Matters#

The suffix array is the workhorse data structure for advanced string problems. A single suffix array plus LCP array supports:

• Substring search in O(m log n) by binary searching for the pattern's position.
• Number of distinct substrings in O(n) using n*(n+1)/2 - sum(LCP).
• Longest repeated substring in O(n) as max(LCP).
• Longest common substring of two strings in O(n + m) by concatenating with a sentinel and scanning LCP across boundary.
• Lex-order traversal of all substrings, k-th smallest substring, and many more.

Suffix arrays predate suffix trees as the practical choice in production. Suffix trees use 5x to 10x more memory and have worse cache behaviour. Suffix arrays fit in 5n bytes for short strings and benefit from sequential memory access. Bowtie2, BWA, and other genome aligners use suffix-array-based indices (FM-index) to handle billions of DNA reads.

In interviews, suffix arrays are deep-end territory — usually for senior or staff-level loops at Google, Meta, ByteDance, and ICPC-grad-favouring teams. Showing fluency with prefix doubling construction or even just stating the existence of O(n log n) construction signals research-grade preparation.

The strategic angle: suffix arrays are the bridge between competitive programming and systems work. Once you can build one and apply Kasai, the entire string-algorithms research literature opens up.

The Core Insight#

The naive O(n^2 log n) construction sorts suffixes using direct string comparison — each comparison costs O(n). Manber-Myers replaces direct comparison with rank-based comparison.

Prefix doubling. After k rounds, every suffix has a rank that uniquely identifies its first 2^k characters. Two suffixes can be compared by their ranks in constant time. To advance to the next round, we sort suffixes by the pair (rank[i], rank[i + 2^k]), where missing ranks beyond the string default to -1. Sorting n pairs takes O(n log n) with comparison sort, O(n) with radix sort. After O(log n) rounds, ranks distinguish all suffixes, and the rank array becomes the inverse of the suffix array.

The intuition: after round 0, ranks reflect single-character order. After round 1, they reflect 2-character prefixes. After round 2, 4-character prefixes. Doubling each round means after log2(n) rounds we have enough resolution for the entire string.

Kasai LCP. Given SA, computing LCP naively is O(n^2). Kasai's algorithm is O(n) using one observation: if LCP[rank[i]] = h for suffix i, then LCP[rank[i + 1]] >= h - 1. Why? Removing the leading character from a common prefix yields a common prefix of length h - 1. So we walk through suffixes in original order (not sorted order), maintain a counter h, decrement by one each step, and only ever increase h by direct character comparison — paying total work O(n) across the run.

The combination of suffix array plus LCP gives a "static" representation of all substrings ordered lexicographically. From there, classical queries become array scans or binary searches.

Visual Dry Run#

String s = "banana$" (the $ sentinel is smaller than any letter).

Suffixes:

0: banana$
1: anana$
2: nana$
3: ana$
4: na$
5: a$
6: $

Sorted lexicographically:

6: $
5: a$
3: ana$
1: anana$
0: banana$
4: na$
2: nana$

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

LCP computation. For each consecutive pair in sorted order:

LCP between "$" and "a$"        = 0
LCP between "a$" and "ana$"     = 1   ("a")
LCP between "ana$" and "anana$" = 3   ("ana")
LCP between "anana$" and "banana$" = 0
LCP between "banana$" and "na$" = 0
LCP between "na$" and "nana$"   = 2   ("na")

LCP = [0, 0, 1, 3, 0, 0, 2] (with LCP[0] = 0 by convention).

Number of distinct substrings: total substrings of "banana" (excluding sentinel) = 6*7/2 = 21. Subtract sum of LCP excluding the sentinel-paired entries — careful counting gives 15 distinct non-empty substrings of "banana".

Longest repeated substring: max(LCP) = 3, the string "ana" (occurs twice in "banana").

Solution (Optimal)#

Python — Prefix Doubling Suffix Array and Kasai LCP#

def build_suffix_array(s: str) -> list[int]:
    n = len(s)
    sa = list(range(n))
    rank = [ord(c) for c in s]
    tmp = [0] * n
    k = 1
    while True:
        def key(i: int) -> tuple[int, int]:
            return (rank[i], rank[i + k] if i + k < n else -1)
        sa.sort(key=key)
        tmp[sa[0]] = 0
        for i in range(1, n):
            tmp[sa[i]] = tmp[sa[i - 1]] + (1 if key(sa[i]) != key(sa[i - 1]) else 0)
        rank = tmp[:]
        if rank[sa[-1]] == n - 1:
            break
        k *= 2
    return sa
 
def kasai_lcp(s: str, sa: list[int]) -> list[int]:
    n = len(s)
    rank = [0] * n
    for i, suf in enumerate(sa):
        rank[suf] = i
    lcp = [0] * n
    h = 0
    for i in range(n):
        if rank[i] > 0:
            j = sa[rank[i] - 1]
            while i + h < n and j + h < n and s[i + h] == s[j + h]:
                h += 1
            lcp[rank[i]] = h
            if h > 0:
                h -= 1
    return lcp

JavaScript — Prefix Doubling Suffix Array and Kasai LCP#

function buildSuffixArray(s) {
  const n = s.length;
  const sa = Array.from({ length: n }, (_, i) => i);
  let rank = Array.from(s, c => c.charCodeAt(0));
  let tmp = new Array(n).fill(0);
  let k = 1;
  while (true) {
    const key = i => [rank[i], i + k < n ? rank[i + k] : -1];
    sa.sort((a, b) => {
      const ka = key(a), kb = key(b);
      return ka[0] - kb[0] || ka[1] - kb[1];
    });
    tmp[sa[0]] = 0;
    for (let i = 1; i < n; i++) {
      const a = key(sa[i]), b = key(sa[i - 1]);
      tmp[sa[i]] = tmp[sa[i - 1]] + (a[0] !== b[0] || a[1] !== b[1] ? 1 : 0);
    }
    rank = tmp.slice();
    if (rank[sa[n - 1]] === n - 1) break;
    k *= 2;
  }
  return sa;
}
 
function kasaiLCP(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 h = 0;
  for (let i = 0; i < n; i++) {
    if (rank[i] > 0) {
      const j = sa[rank[i] - 1];
      while (i + h < n && j + h < n && s[i + h] === s[j + h]) h++;
      lcp[rank[i]] = h;
      if (h > 0) h--;
    }
  }
  return lcp;
}

Complexity: O(n log^2 n) with comparison sort, O(n log n) with radix sort. Kasai is O(n) given the suffix array.

Common Mistakes#

Forgetting the sentinel. Without a sentinel character smaller than any string character, the suffix array is correct lexicographically but algorithms that rely on the sentinel-terminated property (some FM-index variants, certain LCP applications) misbehave. Append $ or chr(0) and adjust indices accordingly.

Using string slicing in the comparator. lambda a, b: s[a:].compare(s[b:]) is O(n) per comparison, blowing the construction up to O(n^2 log n). Use rank-based comparison after the first round.

Off-by-one in the rank update. When recomputing ranks after sort, two consecutive equal pairs should map to the same rank. Forgetting the + (1 if pair differs else 0) increment merges all ranks to zero on repeated input.

Stopping the doubling loop too early. The exit condition is "all ranks are distinct" which happens when rank[sa[n-1]] == n - 1. Stopping based on k >= n works but does extra rounds.

Kasai LCP without the h > 0 check before decrementing. If h = 0 and you decrement, h becomes negative, breaking the invariant. The if h > 0: h -= 1 guard is essential.

Computing LCP wrong when the previous suffix overlaps. The trick of "removing the first character preserves at least h - 1 common prefix" only applies when the suffix at rank[i] - 1 is the same as the previous round's neighbour. Stick to Kasai's exact iteration order — process in original-string order, not sorted order.

Interview Tips#

If a problem asks for "all suffixes sorted" or "longest repeated substring," reach for suffix arrays. Even mentioning them — "I would build a suffix array in O(n log n) and apply Kasai LCP for O(1) repeated substring length" — earns credit when the problem allows it.

For coding interviews under tight time pressure, the naive O(n^2 log n) suffix array is acceptable when n <= 1000. Write the prefix-doubling version only when constraints push beyond that.

When asked the difference between suffix arrays and suffix trees, emphasise: suffix arrays are 5-10x smaller in memory, faster in practice due to cache locality, and pair with LCP arrays to recover most suffix tree functionality. Suffix trees give cleaner asymptotic bounds for some operations (longest common extension in O(1) with LCA queries) but are harder to implement.

For the "number of distinct substrings" question, the answer is one line: n * (n + 1) / 2 - sum(LCP). Each suffix contributes n - SA[i] substrings (its prefixes), but LCP[i] of those duplicate the prefixes of the previous suffix in sorted order. Total distinct = sum of (length - LCP) across the SA.

For "longest common substring of s and t," concatenate s + '#' + t + '$', build suffix array and LCP, then scan adjacent suffixes and report the maximum LCP where the two suffixes come from different sides of the #. O(n + m) after preprocessing.

Follow-up Questions#

Q: How do you do substring search using a suffix array? A: Binary search for the pattern as a key. Each comparison is O(m), giving O(m log n) total. With LCP arrays you can speed comparisons to O(m + log n). Suffix arrays are ideal for "many patterns against one indexed text."

Q: What is the FM-index? A: A compressed suffix array based on the Burrows-Wheeler transform. It supports backwards search in O(m) and uses O(n log sigma) bits where sigma is alphabet size. Standard in genome aligners.

Q: Can suffix arrays be built in O(n)? A: Yes. SA-IS (suffix array induced sorting) is O(n) with reasonable constants. DC3 is also O(n). Both are non-trivial to implement; prefix doubling is the practical workhorse.

Q: How does the suffix array support range minimum queries on LCP? A: Build a sparse table over LCP. Then the longest common prefix of any two suffixes s[i..] and s[j..] is min(LCP[rank[i]+1..rank[j]]). With a sparse table this is O(1) per query.

Q: Suffix array vs suffix automaton — when to choose? A: Suffix arrays are easier to think of statically and pair beautifully with LCP. Suffix automata are better for "is this substring present?" queries and counting occurrences in O(m). For one-shot batch analysis, SA. For online substring queries on a built model, SAM.

Key Takeaways#

• A suffix array SA lists the indices of all suffixes in lexicographic order; combined with the Kasai LCP array, it answers a wide range of substring questions in optimal time.
• Prefix doubling (Manber-Myers) builds the suffix array in O(n log n) with radix sort or O(n log^2 n) with comparison sort by sorting on (rank, rank-after-k) pairs and doubling k each round.
• Kasai's LCP algorithm runs in O(n) by exploiting the invariant that removing one leading character drops the common prefix length by at most one.
• Distinct substrings count is n*(n+1)/2 - sum(LCP); longest repeated substring is max(LCP); longest common substring of two strings reduces to LCP scan after sentinel concatenation.
• Suffix arrays beat suffix trees in practice on memory and cache behaviour and form the backbone of FM-index-based genome aligners and text-search engines.
• Interview signal: even mentioning suffix arrays plus LCP demonstrates research-grade preparation valued at Google, Meta, and competitive-programming-aware teams.