Suffix Array Construction: Doubling to SA-IS

Naive Sorting and Its Hidden Cost

A suffix array sorts the starting positions $0,\dots,n-1$ by their suffixes. Direct comparison sorting hides the cost of each key comparison: two repetitive suffixes may share $\Theta(n)$ leading symbols before differing or reaching an end. Thus $O(n\log n)$ key comparisons can require $O(n^2\log n)$ character work. Materializing every suffix also copies $\Theta(n^2)$ symbols.

Prefix-based construction replaces rescanning with integer ranks. Once length-$k$ prefixes have equivalence classes, length-$2k$ prefixes are represented by pairs of class IDs.

Prefix Doubling

Append a unique minimum sentinel. Sorting terminated suffixes is equivalent to sorting cyclic shifts because every rotation contains the sentinel once. Coordinate-compress input symbols to positive integers and reserve rank $0$ for the sentinel.

Suppose class array $C$ ranks cyclic prefixes of length $k$. A length-$2k$ prefix at $i$ is represented by $(C[i],C[(i+k)\bmod N])$. Subtracting $k$ from positions in the existing order already sorts by the second component; stable counting sort by the first class completes the pair sort in $O(N)$.

Scan adjacent pairs to assign new classes, double $k$, and repeat until $k\ge N$ or every class is unique. The $O(\log N)$ rounds cost $O(N)$ each, giving $O(N\log N)$ time and $O(N)$ space.

from random import Random


def _counting_sort_by_class(positions: list[int], classes: list[int]) -> list[int]:
    class_count = max(classes) + 1
    counts = [0] * class_count
    for position in positions:
        counts[classes[position]] += 1

    starts = [0] * class_count
    for class_id in range(1, class_count):
        starts[class_id] = starts[class_id - 1] + counts[class_id - 1]

    result = [0] * len(positions)
    for position in positions:
        class_id = classes[position]
        result[starts[class_id]] = position
        starts[class_id] += 1
    return result


def suffix_array(text: str) -> list[int]:
    """Construct a suffix array in O(n log n) with radix-sorted doubling."""
    if not text:
        return []

    alphabet = {
        symbol: rank
        for rank, symbol in enumerate(sorted(set(text)), start=1)
    }
    values = [alphabet[symbol] for symbol in text] + [0]
    n = len(values)
    order = sorted(range(n), key=values.__getitem__)

    classes = [0] * n
    class_id = 0
    classes[order[0]] = 0
    for index in range(1, n):
        if values[order[index]] != values[order[index - 1]]:
            class_id += 1
        classes[order[index]] = class_id

    length = 1
    while length < n and class_id + 1 < n:
        shifted = [(position - length) % n for position in order]
        order = _counting_sort_by_class(shifted, classes)

        next_classes = [0] * n
        next_class_id = 0
        next_classes[order[0]] = 0
        for index in range(1, n):
            current = order[index]
            previous = order[index - 1]
            current_pair = (
                classes[current],
                classes[(current + length) % n],
            )
            previous_pair = (
                classes[previous],
                classes[(previous + length) % n],
            )
            if current_pair != previous_pair:
                next_class_id += 1
            next_classes[current] = next_class_id

        classes = next_classes
        class_id = next_class_id
        length <<= 1

    sentinel_position = len(text)
    return [position for position in order if position != sentinel_position]


def naive_suffix_array(text: str) -> list[int]:
    return sorted(range(len(text)), key=lambda index: text[index:])


if __name__ == "__main__":
    for sample in ["", "a", "banana", "aaaaaa", "mississippi", "abracadabra", "😀a😀é"]:
        result = suffix_array(sample)
        assert result == naive_suffix_array(sample)
        assert sorted(result) == list(range(len(sample)))
        assert [sample[i:] for i in result] == sorted(sample[i:] for i in result)
        print(sample, result)

    rng = Random(20260916)
    for _ in range(1_000):
        sample = "".join(rng.choice("abc") for _ in range(rng.randrange(25)))
        assert suffix_array(sample) == naive_suffix_array(sample)

DC3 and SA-IS Ideas

DC3, or skew, samples positions congruent to $1$ or $2$ modulo $3$, radix-sorts their first three symbols, recursively sorts non-unique names, then sorts modulo-$0$ suffixes and merges using constant-size rank comparisons. The reduced problem has about two-thirds the positions, yielding linear total work.

SA-IS classifies the sentinel suffix as S-type. Position $i$ is S-type when $S[i]\lt S[i+1]$, or when symbols tie and $i+1$ is S-type; otherwise it is L-type. An LMS position is S-type with an L-type predecessor.

Place LMS suffixes at bucket tails, induce L-type suffixes left-to-right into bucket heads, then induce S-type suffixes right-to-left into bucket tails. Name LMS substrings in discovered order. If names are not unique, recursively suffix-sort the reduced name string. Place LMS suffixes in exact order and repeat induction. LMS positions are nonadjacent, so the reduced problem is at most half-sized and the total time is linear for an integer alphabet.

flowchart TD
    CLASSIFY["Classify suffixes as L or S"]
    LMS["Identify LMS positions"]
    PLACE["Place LMS suffixes at bucket tails"]
    INDUCE1["Induce L left-to-right, then S right-to-left"]
    NAME["Name LMS substrings"]
    UNIQUE{"Are names unique?"}
    RECURSE["Recursively sort reduced string"]
    FINAL["Place LMS suffixes in exact order"]
    INDUCE2["Induce final L and S order"]
    SA["Completed suffix array"]
    CLASSIFY --> LMS
    LMS --> PLACE
    PLACE --> INDUCE1
    INDUCE1 --> NAME
    NAME --> UNIQUE
    UNIQUE -->|no| RECURSE
    UNIQUE -->|yes| FINAL
    RECURSE --> FINAL
    FINAL --> INDUCE2
    INDUCE2 --> SA

Engineering the Construction

The sentinel must be unique and smaller than all real symbols. Coordinate compression with reserved rank $0$ works for Unicode, bytes, tokens, and integer sequences. Memory often dominates: doubling retains order, class, next-class, count, and encoded-text arrays, and language-level integers can multiply the footprint.

Validate that the array has length $n$, contains every position exactly once, and orders adjacent suffixes. Before removal, the sentinel position must be first. Differential-test random small inputs against a naive oracle and include empty, single-symbol, repetitive, sorted, reverse-sorted, and large-alphabet cases.