Suffix Array Construction (Prefix
Doubling)'s own closing paragraph names the gap this page closes: prefix doubling gets suffix
array construction down to O(n log² n) by comparing rank pairs instead of raw
text, but "SA-IS's stronger O(n) bound is a further step past that one, still not
built here." SA-IS (Suffix Array by Induced Sorting, Nong/Zhang/Chen 2009) gets
there with a different mechanism entirely: classify every suffix as one of two types, use that
classification to induce the position of most suffixes from a small subset's order rather
than comparing anything directly, and recurse on a genuinely smaller problem only when that subset's
own order isn't yet fully known. The output is the identical array Suffix Array's own binary search relies on, built faster
still than prefix doubling — not a new way to search once built.
Enter a text (lowercase letters, up to 12 characters) and press
Build, then press Step to walk through every phase: classifying
each suffix's type, seeding and inducing a first guess at the LMS order, naming the LMS substrings,
recursing if needed, then seeding and inducing again with the now-correct order. The default,
mississippi, is the classic example specifically because it needs that recursion —
try banana alongside it to see a text where the first naming pass already settles
everything. The two checkboxes reproduce this page's two Pitfalls live.
Call a suffix S-type if it's lexicographically smaller than the suffix starting
one position to its right, L-type if it's larger. That's decidable without ever
comparing full suffixes: the very last position (a sentinel, unique and smaller than every real
character) is always S-type, and every other position compares its own character against the next
position's — a strict inequality decides it outright, and a tie inherits whatever the next position
already resolved to. A position is called LMS (leftmost S) if it's S-type but the
position immediately before it is L-type — the left edge of a run of S's. On
mississippi the run breaks down into L/S stretches with LMS positions at the starts of
issi, issi (again), ippi, and the trailing sentinel — the
repeated issi is exactly what will force this example into recursion below.
The genuinely surprising part is induced sorting: place the LMS positions into their character buckets in any order at all, then scan the array left to right — whenever a placed suffix's predecessor is L-type, that predecessor's correct bucket slot is now decidable purely from what's already been placed, so drop it in. Do the same scanning right to left for S-type predecessors. After both passes, the LMS positions land back out of the array in their true relative order by LMS substring — not because the initial guess was good, but because every non-LMS suffix's position was always fully determined by its neighbor's, and the induction just walks that dependency chain to a fixed point regardless of where it started. That's the one claim on this page taken from the source paper's proof rather than re-derived here; verified empirically instead, across every random trial below.
"True relative order by LMS substring" is a specific, narrower claim than "true suffix order" —
an LMS substring runs from one LMS position to the next inclusive, and two LMS suffixes
whose substrings are identical still need their full suffixes told apart, which the substring
comparison alone can't do. So each LMS substring gets a name — walk the induced
order, and any two adjacent LMS substrings that compare unequal (checked character by character,
requiring both to hit their own LMS boundary at the same offset to count as equal — not just
agreeing for a few characters) get a new name; identical ones share it. If every name is already
distinct, the induced order already is the true LMS suffix order, nothing left to prove.
If not — as happens to both copies of issi in mississippi, whose LMS
substrings are identical — build a smaller string out of just those names, in their original
left-to-right positions, and recurse: solving that string's suffix array (the same
algorithm, one level down) is exactly solving "which of these tied LMS suffixes actually comes
first," since two suffixes of the reduced string disagree in exactly the order their corresponding
LMS suffixes do. The reduced string is provably at most half the original length (no two LMS
positions are adjacent, by definition), which is what makes the recursion terminate in
O(log n) levels and the whole algorithm sum to O(n) rather than blow up.
Either way — names already unique, or resolved by recursion — the true LMS order is now known. Seed the buckets again, this time with that correct order instead of an arbitrary one, and run the exact same two induce passes a second time. Nothing about induction changes; what changed is that the seed is now provably correct everywhere, not just for LMS substrings, so this second pass places every suffix in the array correctly, LMS and non-LMS alike.
This is the exact scheme the demo above steps through, with the recursion written directly rather than unrolled:
function suffixArrayInducedSorting(text) {
const codes = [...text].map(c => c.charCodeAt(0) - 96); // 'a'=1 .. 'z'=26
codes.push(0); // unique sentinel, smaller than everything
return buildSA(codes, 27).slice(1); // drop the sentinel-only suffix
function buildSA(s, K) {
const n = s.length;
if (n === 1) return [0];
// classify each suffix S-type (smaller than the suffix one to its right) or L-type (larger)
const isS = new Array(n);
isS[n - 1] = true; // the sentinel is always S-type
for (let i = n - 2; i >= 0; i--) {
isS[i] = s[i] < s[i + 1] || (s[i] === s[i + 1] && isS[i + 1]);
}
const isLMS = i => i > 0 && isS[i] && !isS[i - 1]; // leftmost S in a run of S's
const sizes = new Array(K).fill(0);
for (const c of s) sizes[c]++;
const bucketHeads = () => { const h = new Array(K); let sum = 0; for (let c = 0; c < K; c++) { h[c] = sum; sum += sizes[c]; } return h; };
const bucketTails = () => { const t = new Array(K); let sum = 0; for (let c = 0; c < K; c++) { sum += sizes[c]; t[c] = sum; } return t; };
function seedAndInduce(lmsOrder) {
const SA = new Array(n).fill(-1);
const tails = bucketTails();
for (let i = lmsOrder.length - 1; i >= 0; i--) { const j = lmsOrder[i]; SA[--tails[s[j]]] = j; }
const heads = bucketHeads();
for (let i = 0; i < n; i++) { const j = SA[i] - 1; if (j >= 0 && !isS[j]) SA[heads[s[j]]++] = j; }
const tails2 = bucketTails();
for (let i = n - 1; i >= 0; i--) { const j = SA[i] - 1; if (j >= 0 && isS[j]) SA[--tails2[s[j]]] = j; }
return SA;
}
const lmsPositions = [];
for (let i = 1; i < n; i++) if (isLMS(i)) lmsPositions.push(i);
// pass 1: an arbitrary initial LMS order still induces the correct *relative* order of LMS substrings
let SA = seedAndInduce(lmsPositions);
const sortedLMS = [];
for (let i = 0; i < n; i++) if (isLMS(SA[i])) sortedLMS.push(SA[i]);
// name each LMS substring; identical substrings get identical names
const names = new Array(n).fill(-1);
let name = 0;
names[sortedLMS[0]] = 0;
for (let i = 1; i < sortedLMS.length; i++) {
const prev = sortedLMS[i - 1], cur = sortedLMS[i];
let diff = false, d = 0;
while (true) {
const prevEnd = d > 0 && isLMS(prev + d), curEnd = d > 0 && isLMS(cur + d);
if (prevEnd || curEnd) { diff = !(prevEnd && curEnd); break; }
if (s[prev + d] !== s[cur + d] || isS[prev + d] !== isS[cur + d]) { diff = true; break; }
d++;
}
if (diff) name++;
names[cur] = name;
}
// recurse only if some LMS substrings collided under naming; otherwise names are already the answer
let sortedLMSFinal;
if (name + 1 === sortedLMS.length) {
sortedLMSFinal = sortedLMS;
} else {
const reduced = lmsPositions.map(p => names[p]);
const reducedSA = buildSA(reduced, name + 1);
sortedLMSFinal = reducedSA.map(idx => lmsPositions[idx]);
}
// pass 2: seed with the now-*correct* LMS order and induce again -- every suffix lands correctly
return seedAndInduce(sortedLMSFinal);
}
}Verified against an independently sorted reference order (plain string comparison over every
suffix) across 100,000 random trials (length 1–20, alphabet size 1–26, weighted toward
small alphabets to force real collisions and real recursion) — 0 mismatches, including
mississippi and every other example on this page.
Naming LMS substrings by comparing only a fixed number of characters, instead of
requiring both substrings to reach their own LMS boundary at the same offset to count as
equal, treats one substring as a match for a longer one it's merely a prefix of. Two LMS
substrings of different lengths can agree on their first several characters and then genuinely
diverge — a fixed lookahead window can run out before that divergence and call them equal when
they're not, silently under-recursing on a problem that needed the distinction. On
bababab, comparing only a bounded window gives [5,3,1,6,4,0,2] against
the correct [5,3,1,6,4,2,0] — the last pair swapped. Checked, not just reasoned about:
across 30,000 random (length 2–20, alphabet size 1–4) trials against an independently
sorted reference order, this variant disagrees on 2.2% of them — real, but the
rarest-triggering bug measured on this site's exact-match entries so far, since a fixed window has
to land exactly between two substrings' point of divergence to matter. Try
bababab above with the first box unchecked to see this exact swap live.
Classifying a tied character as L-type outright, instead of inheriting whatever the
following suffix's type already resolved to, breaks the one invariant every later phase assumes:
that S-type genuinely means "smaller." The tie-inherit rule exists because a character
comparison alone can't settle a tie — only what comes after can — and skipping it doesn't just
misclassify one position, it can misclassify entire runs at once, since the bug also compounds
through the same backward scan that would otherwise propagate the correct answer. On
caac, the correct build finishes [1,2,3,0]; misclassifying ties leaves
one array slot never filled at all — [1,2,3,-1] — because a suffix silently lost
LMS status it should have had, so nothing ever gets seeded into that bucket to induce from. Checked
the same way: 40.6% of the same 30,000 trials disagree with the reference order (a
higher rate than the first bug, since every tie anywhere in the text is a chance to trigger it, not
just one specific boundary). Try caac above with the second box unchecked to see the
unfilled slot live.
Time: O(n) — each level of recursion does O(nlevel)
work (classification, two induce passes, and naming are each one linear scan), and the reduced
string at the next level is provably at most half the current length, so the levels' total sizes
form a geometric series summing to O(n) overall, regardless of how many levels recursion
actually needs. Measured directly, counting every array read/write across all recursion levels
combined: on Suffix Array's own n = 200 /
400 / 800 / 1,600 / 3,200 repeated-'a' worst case, this page takes 2,008 /
4,008 / 8,008 / 16,008 / 32,008 operations — exactly 2.00×
per doubling, every single time, the unmistakable signature of linear growth (this input needs no
recursion at all — the sentinel is the only LMS position — so it's actually this page's cheapest
case, not its worst one, unlike the naive sort it makes obsolete). On random 26-letter text at the
same sizes: 2,520 / 5,946 / 11,957 / 24,072 / 48,319, converging to the same
~2.01× per doubling once past small-n constant overhead. Against
Suffix Array Construction (Prefix
Doubling)'s own measured 1,772 / 3,829 / 8,287 comparator calls at n
= 200/400/800 on that identical repeated-character input, the two pages are close at this scale — SA-IS's
2,008/4,008/8,008 is actually a bit higher at n=200 and roughly even by n=800 —
but prefix doubling grows at a measured ~2.16× per doubling (the
log² n factor, still slowly widening) against SA-IS's flat 2.00×:
a real gap, just one that needs considerably larger n than this demo's 12-character
limit to look dramatic rather than marginal. Space: O(n) total — the
per-level arrays (isS, bucket tables, the SA array itself) again form the
same halving geometric series as the time bound, plus O(n) stack depth across
O(log n) recursive calls.
The resulting array, and everything Suffix Array's own binary search does with it, is unchanged — this page is a faster path to the same structure, not a different one, exactly as Suffix Array Construction (Prefix Doubling) already is. See Choosing an Exact-Match String Matcher for how Suffix Array itself weighs against the other exact-match entries; this page is a further refinement on that same comparison, not a new branch in it.