Information gap in suffix array article

[bruisedsamurai]

After we use count sort. It's not clear as why are we comparing strings and what part of strings are we comparing with.

Moreover, how $2^k$ value came into the picture too is still a mystery. How are we making sure strings are of length $2^k$?

[jakobkogler]

We look at the strings in a cyclic form.
So there are substrings of arbitrary lenght here. E.g. if we have the string "abcde" and we take the substring of length 8 starting at index 1 we get "bcdeabcd".

And the goal is, to sort all shifts, which is equivalent to sorting the cyclic substrings of length $2^k$ with $2^k >= n$, e.g. the sorted order of all substrings of length 8 for an array of length 5.

I hope that clears everything up. Tell us, if we should improve the article more. But I think it already tell all those ideas that I wrote.

[bruisedsamurai]

@jakobkogler That explains some of it. I assume we take $2^k$ so that later we can compare $2^{k-1}$ substrings.

I think a concrete example with comparisons of two strings (that includes sentinel '$')will definitely help here.