This might not be the most efficient implementation of a Suffix Array, but I thing it has its charme.
The basic concept of a Suffix Array is a simple ordered set of suffix strings. If we have an ordered list of all possible suffixes within the string we can implement substring searches with a simple binary search to determine if a given substring can be found within the string.
So in a way one might build up a suffix array simply as.
Of course that's not achieving much since (1) we loose the index (the most precious part for later substring searches) and (2) we waste lots of space since each substring gets stored individually. So for a string of length 10 we would have to store sum(1...10)==55 characters for all suffixes. It doesn't even have academical values but may be some other variant of std::set<...> can be used instead:.
So what do we need ?
All in all this sounds like a std::set<int> with a custom comparator class.
The declaration of std::set<...> is:
With the Compare class being used to establish element order and uniqueness. It defaults to less<T> which tries to apply the < operator on it's two arguments.
If however we provide our own custom comparator with the string we would like to construct a suffix array from we might use it to order the index value by the substring comparison like this:
When building the Suffix Array we might simply do:
... which gives us:
Voila – suffix index values in the proper order.