The Doubling Algorithm for Suffix Array Construction
I'll use x = "banana", m = 6
as an example. The suffixes are:
0: banana
1: anana
2: nana
etc.
First, we'll work out R1
, which is the rank of each suffix according to it's first letter only. Because we're just comparing single letters, we can do it in Theta(m)
with a bucket sort. There will be some duplicates, and that's fine. We only have three different letters, so we give all of the A's a rank of 0, all of the B's a rank of 1, and all of the N's a rank of 2. We end up with this: