Suffix Array Construction
Sort suffixes by doubling the compared prefix length each round.
Suffix 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.
Cost
- Best
- O(n log n)
- Average
- O(n log n)
- Worst
- O(n log n)
- Space
- O(n)
Before this
Taught by the same lesson
Suffix Array covers these too, in the same run.