AlgoScope

Suffix Array Construction

Sort suffixes by doubling the compared prefix length each round.

String algorithms, algorithm, advanced
Break the tie between 1 and 3 using the ranks 1 ahead.k=1k=2k=4k=8k=160 b1 a2 n3 a4 n5 a102020
Break the tie between 1 and 3 using the ranks 1 ahead.k=1k=2k=4k=8k=160 b1 a2 n3 a4 n5 a102020

Suffix Array: Prefix doubling: ranks by 1, 2, 4, 8 characters

Decision, step 2 of 6

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.

How suffix array works

Cost

Best
O(n log n)
Average
O(n log n)
Worst
O(n log n)
Space
O(n)

Taught by the same lesson

Suffix Array covers these too, in the same run.