Suffix Array's own Pitfalls section names a real,
measured trap: sorting suffixes by slicing and comparing full strings costs up to O(n)
character work per comparison, and on repetitive text that makes the whole sort O(n²
log n) instead of the O(n log n) a suffix array construction is supposed to
cost. This page builds the fix that page's own text names but doesn't build: instead of re-reading
characters from scratch on every comparison, prefix doubling keeps a rank table
that already knows, from the previous round, how every suffix compares up to some prefix length —
and doubles that known length each round by combining two already-computed ranks instead of
rescanning any text. The output is the identical suffix array Suffix Array's own binary search
relies on; only how it gets built changes.
Enter a text (lowercase letters, up to 12 characters) and press
Build, then press Step to walk through one round at a time. Each
round doubles k — the number of characters' worth of order already known — by sorting
on the pair (rank[i], rank[i+k]): the first half of the comparison is what the previous
round already settled, the second half is one round-k-ago rank lookup instead of a
fresh character scan. The two checkboxes reproduce this page's two Pitfalls live — uncheck one to
see the final order come out wrong, flagged in red against an independently sorted reference order
computed fresh every time.
Call a suffix's 2r-rank its position if every suffix were
sorted only by its first 2r characters (ties allowed for suffixes that agree
that far). Round r of this algorithm — parameterized by k = 2r-1
— computes the 2r-rank from the previous round's already-correct
k-rank, by induction: suffix i's first k characters are
already ordered by rank[i], and its next k characters — text
positions i+k through i+2k-1 — are exactly suffix i+k's own
first k characters, already ordered by rank[i+k]. Sorting the pair
(rank[i], rank[i+k]) is therefore sorting by the true first 2k characters,
without ever touching the text itself. A suffix with fewer than k characters left
before i+k has no real "next chunk" at all — it's a proper prefix of whatever's sorted
near it, and a proper prefix must sort as strictly smaller than anything it prefixes (exactly
matching how plain string comparison treats "aa" as less than "aaa"), so
that missing chunk needs a key below every real rank, not a stand-in for one. Once every suffix's
rank is unique, no further round can change anything — the order is already the full suffix
array — which is why the demo above stops as soon as that happens rather than always running
⌈log&sub2; n⌉ rounds.
That early stop means the round count actually taken depends on the text, not just its length:
a string with no repeated characters at all can finish in a single round (every suffix is already
distinguished by its first character), while n copies of the same character is the
genuine worst case, needing the full ⌈log&sub2; n⌉ rounds because no two
suffixes separate until the doubling window finally exceeds the distance between them.
This is the exact scheme the demo above steps through:
function buildSuffixArrayDoubling(text) {
const n = text.length;
const chars = Array.from(new Set(text)).sort();
const rankOf = new Map(chars.map((c, i) => [c, i]));
let rank = Array.from(text, c => rankOf.get(c)); // round 0: rank by one character
let sa = Array.from({ length: n }, (_, i) => i);
for (let k = 1; ; k *= 2) {
const key2 = i => (i + k < n) ? rank[i + k] : -1; // -1: "nothing here" sorts lowest
sa = sa.slice().sort((a, b) =>
rank[a] !== rank[b] ? rank[a] - rank[b] : key2(a) - key2(b));
const newRank = new Array(n);
newRank[sa[0]] = 0;
for (let i = 1; i < n; i++) {
const tied = rank[sa[i - 1]] === rank[sa[i]] && key2(sa[i - 1]) === key2(sa[i]);
newRank[sa[i]] = newRank[sa[i - 1]] + (tied ? 0 : 1); // dedupe: ties keep one rank
}
rank = newRank;
if (rank[sa[n - 1]] === n - 1) break; // every rank now unique -- done
if (k >= n) break; // safety net, same conclusion either way
}
return sa;
}Skipping rank deduplication — assigning each suffix its sorted position as the new rank,
instead of giving tied suffixes the same rank — locks in a wrong order after the very first
round and never fixes it. On "aaa": round 1 correctly sorts the three
suffixes by their first two characters, discovering "a" is smallest but leaving
"aa" and "aaa" tied (both start "aa"). The correct rule keeps
that tie — both get rank 1 — so round 2 can still tell them apart using their third
character's worth of information. Skipping the dedupe instead hands them the arbitrary ranks 1 and
2 straight from sort position, even though nothing about their content actually differs yet. Every
later round sorts primarily by that already-all-distinct rank, so the tiebreak that should have
waited for real evidence is now permanent — round 2's correct insight (a suffix that runs out of
characters, like "aa" does, must sort below one that doesn't, like "aaa")
never gets consulted, because the primary key alone already decided the order. The demo's default
"mississippi" shows this isn't just a degenerate all-one-character case: with
deduplication off it produces [10,7,1,4,0,9,8,3,6,2,5] against the correct
[10,7,4,1,0,9,8,6,3,5,2] — three pairs of positions 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 79.7% of them,
while the correct algorithm above matched that same reference on all 30,000.
Treating a suffix that runs past the end of the text as rank 0, instead of as
categorically lower than every real rank, ties it against whichever real content happens to
already hold rank 0 — and loses whenever that tie is broken the wrong way. Rank 0 is
earned by some actual character or chunk; a suffix with nothing left to compare isn't tied with
that content, it's a proper prefix of whatever it's being measured against; and a proper prefix
must sort strictly below any string it prefixes, the same way plain string comparison already
treats "baab" as less than "baabaab". On "baabaab", the
correct order ends …,6,3,0 (index 3, the suffix "baab", sorts just
before index 0, the suffix "baabaab" it's a prefix of); treating the missing chunk as
rank 0 instead of a true sentinel swaps that pair to …,6,0,3. Measured the same
way: 38.4% of 30,000 trials disagree with the reference order. Try
baabaab above with the second box unchecked to see this exact swap live.
Time: as shipped, each round is one comparator-based Array.sort
over all n suffixes — O(n log n) comparisons, each O(1) since
a comparison only ever reads two already-computed ranks, never the text itself — followed by one
O(n) linear pass to assign new ranks. With up to O(log n) rounds, that's
O(n log² n) total, not the O(n log n) textbook figure Suffix Array's
own page cites for "prefix doubling" — that bound needs a radix/counting sort within each round
(each key is a small integer pair, not requiring general comparison) to make every round
O(n) instead of O(n log n); not shipped here, for the same reason the
naive sort was shipped on Suffix Array's own page instead of SA-IS — clarity of one recognizable
step (Array.sort) over a specialized one. Measured directly against that page's own
repeated-character worst case (n copies of 'a', the exact input its
Pitfalls section uses): at n = 200 / 400 / 800 this page's construction takes
1,772 / 3,829 / 8,287 total comparator calls
against that page's own measured 20,099 / 80,199 /
320,399 character comparisons on the identical input — each doubling of
n multiplies this page's cost by roughly 2.16× (the
n log n signature) against the naive sort's roughly 4× (the
n² signature), a 38.7× gap already open by n =
800. That gap is specific to repetitive text, though, not universal: on random text at the same
sizes this page's comparator-call count sits within a small constant factor of the naive sort's
character-comparison count either way — measured at roughly 0.9–1.3× across repeated
trials at n = 50 to 800, with no consistent winner — because a naive comparison on
random text usually diverges within the first character or two and stops early, while every round
here always pays a full O(n log n) sort regardless of how quickly real suffixes would
diverge. The advantage this page exists for is specifically bounding the worst case, not
beating the common one.
Space: O(n) for the rank array and each round's freshly sorted index
array, the same footprint Suffix Array's own page already keeps for the array itself.
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. See Choosing an Exact-Match String Matcher for how Suffix Array itself weighs against the other exact-match entries; this page is a refinement on that comparison; not a new branch in it.