StringsAlgorithmaka SA, sorted suffixes, Kasai LCP

Suffix Array

Sort all suffixes of a string by index; with the LCP array it answers substring search, distinct-substring counts and longest-repeat queries.

Pattern: Binary SearchPractice (2)
Progress

Overview

A suffix array sa lists the starting indices of all n suffixes of a string in lexicographic order. For "banana", the sorted suffixes are a, ana, anana, banana, na, nana, so sa = [5, 3, 1, 0, 4, 2]. Its companion, the LCP array, stores the length of the longest common prefix between each pair of adjacent suffixes in that order: lcp = [0, 1, 3, 0, 0, 2].

Together they are a compact substitute for a Suffix Tree: any pattern occurs in the text exactly at a contiguous range of the suffix array, found by binary search in O(m log n); the number of distinct substrings is n(n+1)/2 - Σ lcp; the longest repeated substring is max(lcp); and the longest common substring of two strings is found by building the array of s + "#" + t.

suffixessortingLCP arrayprefix doublingO(n log n)

Intuition

A mental model before the formal terms.

Every substring is a prefix of some suffix. If you write all suffixes on cards and sort the cards, every substring becomes a prefix shared by a contiguous run of cards — like all words starting with "ban" sitting together in a dictionary. Finding a pattern is then a dictionary lookup, and the LCP array tells you how much each card overlaps with its neighbour, which is exactly the redundancy you subtract to count distinct substrings.

Prefix doubling builds the sort quickly: once you know the order of all length-k prefixes, the order of length-2k prefixes is determined by the pair (rank of first half, rank of second half). Ranks double in reach each round, so log n rounds suffice.

How it works

  1. Initialise rank[i] = character code of s[i] and k = 1.
  2. Sort the indices by the key (rank[i], rank[i + k]) where rank[i + k] = -1 past the end. Recompute ranks so that equal keys get equal ranks.
  3. Double k and repeat until all ranks are distinct (at most ⌈log₂ n⌉ rounds). With a comparison sort each round is O(n log n); radix sort gives O(n log n) total.
  4. Kasai's LCP: process suffixes in text order i = 0..n-1. If suffix i has rank r > 0, compare it with suffix sa[r - 1] starting from the previous LCP value minus one; store lcp[r] = h. The reuse h - 1 is valid because dropping the first character of two suffixes with LCP h yields two suffixes with LCP at least h - 1.
  5. Search a pattern: binary search for the lower and upper bound of suffixes that start with p, comparing p with s[sa[mid]..].

Why it works

Comparing two suffixes by (rank_k[i], rank_k[i+k]) is exactly comparing their length-2k prefixes, because rank_k already orders length-k prefixes and lexicographic order compares the first halves, then the second halves. Induction over rounds gives the correct order of full suffixes once 2k ≥ n.

Kasai runs in O(n): h increases by at most n in total (bounded by string length) and decreases by at most 1 per iteration, so the total comparisons are O(n).

Counting distinct substrings: suffix sa[r] contributes n - sa[r] prefixes, of which the first lcp[r] were already counted by the previous suffix. Summing gives n(n+1)/2 - Σ lcp.

Recognition

How to tell a problem wants this.

  • Many pattern queries on one fixed text (offline or online).
  • Questions about all substrings: count distinct substrings, k-th lexicographically smallest substring, longest repeated substring.
  • Longest common substring of two or more strings.
  • Sorting cyclic shifts, or Burrows–Wheeler transform.
“sorted array” → Binary Search“have you seen this before” → Hashing

Interactive visualization

Play, step, change the input. ← → and space work too.

No interactive visualization for this topic yet

Related visualizations are linked under Related.

Pseudocode

1rank[i] = code(s[i]); k = 1
2repeat:
3  sort sa by (rank[i], rank[i+k] or -1)
4  recompute rank from sorted order; if all distinct: break
5  k *= 2
6kasai: h = 0; for i in 0..n-1 (text order):
7  if rank[i] > 0: j = sa[rank[i]-1]; while s[i+h] == s[j+h]: h++; lcp[rank[i]] = h; h = max(h-1, 0)

Implementations

1def build_suffix_array(s: str) -> list[int]:
2    """The suffix array is the sorted order of all suffixes, stored as start
3    indices. Built by prefix doubling: sort by the first 2^k characters, then
4    use those ranks to sort by 2^(k+1), in O(n log^2 n)."""
5    n = len(s)
6    if n == 0:
7        return []
8 
91 · Start from the order given by single characters
10    sa = list(range(n))
11    rank = [ord(c) for c in s]
12    tmp = [0] * n
13 
14    k = 1
15    while True:
162 · Compare (rank[i], rank[i+k]) pairs; -1 stands for "past the end"
17        def key(i: int, k: int = k) -> tuple[int, int]:
18            return (rank[i], rank[i + k] if i + k < n else -1)
19 
20        sa.sort(key=key)
21 
223 · Re-rank: equal pairs share a rank, so ties shrink each round
23        tmp[sa[0]] = 0
24        for i in range(1, n):
25            tmp[sa[i]] = tmp[sa[i - 1]] + (1 if key(sa[i - 1]) < key(sa[i]) else 0)
26        rank = tmp[:]
27        if rank[sa[n - 1]] == n - 1:
28            break  # all ranks distinct: done
29        k <<= 1
30    return sa
31 
32 
334 · Kasai: the LCP array in O(n), reusing the previous suffix's overlap
34def build_lcp(s: str, sa: list[int]) -> list[int]:
35    n = len(s)
36    rank = [0] * n
37    lcp = [0] * max(0, n - 1)
38    for i, suffix_start in enumerate(sa):
39        rank[suffix_start] = i
40    h = 0
41    for i in range(n):
42        if rank[i] == n - 1:
43            h = 0
44            continue
45        j = sa[rank[i] + 1]
46        while i + h < n and j + h < n and s[i + h] == s[j + h]:
47            h += 1
48        lcp[rank[i]] = h
49        if h > 0:
50            h -= 1  # the next suffix shares at least h-1 characters
51    return lcp
52 
53 
545 · Sorted suffixes mean pattern search is two binary searches
55def contains(s: str, sa: list[int], pattern: str) -> bool:
56    lo, hi = 0, len(sa)
57    while lo < hi:
58        mid = (lo + hi) // 2
59        if s[sa[mid] : sa[mid] + len(pattern)] < pattern:
60            lo = mid + 1
61        else:
62            hi = mid
63    return lo < len(sa) and s.startswith(pattern, sa[lo])
Walkthrough
  1. sa.sort(key=key) uses a key function rather than a comparator, which is both the Python convention and faster — the key is computed once per element per round.
  2. def key(i, k=k) captures the current k as a default argument. Without it, the closure would see the *final* k after the loop advances, which is the classic Python late-binding bug.
  3. rank = tmp[:] copies the list; rank = tmp would alias and corrupt the next round.
  4. ord(c) seeds ranks with code points, so the ordering matches Python's own string comparison.
  5. Kasai's h -= 1 after recording each LCP is what bounds the total work at O(n).
Complexity (this implementation)
time O(n log^2 n) to build; O(n) for Kasai; O(m log n) per search · space O(n) for the array, ranks and LCP

The key function is a Python-level call per element per round — roughly n log n calls total — which dominates the runtime.

Language notes
  • list.sort(key=...) computes the key once per element (a built-in Schwartzian transform); functools.cmp_to_key with a comparator is several times slower.
  • Late binding in closures is a genuine hazard here: k changes every round, so it must be bound as a default argument or captured explicitly.
  • Tuple keys compare lexicographically, which is exactly the (rank[i], rank[i+k]) ordering this algorithm needs — no custom comparator required.
  • str.startswith(pattern, pos) avoids the slice allocation that the binary-search comparison above deliberately shows.
Common mistakes in this language
  • Omitting the k=k default binding, so the key function reads the loop variable after it has advanced.
  • Writing rank = tmp instead of rank = tmp[:], aliasing the two lists.
  • Using cmp_to_key to port a C++ comparator directly instead of expressing the order as a tuple key.
Language differences that matter here
  • Ordering API: C++ and JS/TS take comparators (a *boolean* in C++, a signed *number* in JS/TS — a silent porting trap), while Python takes a key projection, which here is just the natural tuple and needs no comparator at all.
  • Closure capture: Python needs the k=k default-argument trick because closures bind late; C++ lambdas capture explicitly, and JS/TS const-per-iteration semantics make the loop variable safe.
  • Copy versus alias when swapping the rank arrays is a hazard in all four, but only C++ makes rank = tmp a genuine copy — in JS/TS and Python the same line aliases.
  • In-place substring comparison exists everywhere (string::compare, startsWith, str.startswith) and is what avoids an allocation per binary-search probe.

Complexity

Best
O(n log n)
Average
O(n log n)
Worst
O(n log² n)
Space
O(n)

Prefix doubling with comparison sort is O(n log² n); with radix sort O(n log n); SA-IS achieves O(n). Kasai LCP is O(n); pattern search is O(m log n).

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • One text, many substring queries — build once, binary search each pattern.
  • Counting distinct substrings, longest repeated substring, k-th smallest substring.
  • Longest common substring of several strings (concatenate with unique separators).
  • When a Suffix Tree would answer the question but memory is tight — a suffix array is a few integers per character.
Avoid it when

Alternatives

Suffix TreeRolling Hash (Polynomial Hashing)Knuth–Morris–Pratt (KMP)Aho–Corasick

Common mistakes

  • Using rank[i + k] without the -1 sentinel for indices past the end — shorter suffixes must sort before their extensions.
  • Stopping prefix doubling after a fixed number of rounds instead of when all ranks are distinct (or k ≥ n).
  • In Kasai, forgetting to reset h = 0 when the suffix has rank 0, or decrementing h below zero.
  • Off-by-one in the distinct-substring formula: it is n(n+1)/2 - Σ lcp, with lcp[0] = 0.

Interview patterns

  • Longest duplicate substring: max(lcp).
  • Count distinct substrings of a string.
  • Longest common substring of two strings via the suffix array of s + "#" + t.
  • Find all occurrences of many patterns in a long text with O(m log n) per pattern.
Interview questions on this
Mock interviews

Example problems

Repeated DNA SequencesmediumLongest Palindromic Substringmedium