Suffix Array Construction: Prefix-Doubling Algorithm

Source String

Auto-step interval 900 ms

Doubling State

Round

Prefix sorted

1 char

Distinct ranks

–

Comparator calls

SA = [ … ] — press Step

How it works

A suffix array SA of a string of length n is the list of its n starting positions, sorted so that the suffixes they point to are in ascending lexicographic order. Naive sorting compares whole suffixes and costs O(n² log n). Prefix doubling does it in O(n log n):

rank⁰[i] = code(s[i])                         (round 0: sort by 1 char)
key[i]   = ( rankᵏ[i], rankᵏ[i+k] )            (or −1 past the end)
rankᵏ⁺¹  = dense rank of key, after sorting all i by key
k        = 2k   (doubles every round)

After round t, every suffix's rank is correct for its first 2ᵗ characters, because the pair (rank of the first k chars, rank of the next k chars) exactly encodes the first 2k chars. Once every suffix has a distinct rank, that rank order is the finished suffix array — no more rounds are needed, so the algorithm needs only ⌈log₂ n⌉ rounds.

Step round — runs exactly one doubling round: builds each suffix's (rank, rank+k) key, sorts by it, and compresses ties into new dense ranks.
Auto — steps automatically at the chosen interval until the array is fully sorted.
Rows — one per suffix, ordered top-to-bottom by current rank; cubes are its characters, tinted brighter over the prefix length already known-correct this round.

Real-world relevance: this construction (and its linear-time cousin, SA-IS) underlies full-text indexes used in genome aligners (e.g. BWA), the `bwtool`/Burrows–Wheeler family, and grep-scale substring search over gigabyte corpora.

Known-sorted prefix (this round) Not yet compared

⚠ Couldn't load the 3D engineThree.js failed to load from the CDN. Check your connection and reload.