Suffix Array Construction
Sort suffixes by doubling the compared prefix length each round.
Decision · step 2 of 6Suffix Array: Prefix doubling: ranks by 1, 2, 4, 8 characters
Positions 1 and 3 both rank 0 on their first 1 character. To rank them on 1 more, look 1 ahead: position 2 ranks 2 and position 4 ranks 2. Still tied; a later round will separate them, or they are equal to the end.
What you will see
Suffixes re-sort in rounds of 1, 2, 4, ... characters; ranks update.
Cost
| Best | O(n log n) |
|---|---|
| Average | O(n log n) |
| Worst | O(n log n) |
| Space | O(n) |
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input, predict what happens next.
Screen readers: Text and pattern cells announce index and character; each step announces the aligned positions, the comparison result and the shift.
Reduced motion: The pattern row snaps to its new alignment with a crossfade instead of sliding.