Java – creation of suffix array nlogn

I've been learning how to create suffix arrays. I understand that we first sort all suffixes according to the first character, then according to the first two characters, then the first four characters, etc., and the number of characters to be considered is less than 2n

But my doubt is why we don't choose the first three characters, then 9... And so on Why only consider 2 characters, because these strings are part of the same string, not different random strings?

Solution

I haven't thoroughly analyzed the suffix array construction algorithm, but I still want to share my thoughts

In my opinion, your question is similar to the following:

>Why do computers use binary encoding of information instead of ternary? > Why does binary search divide alignment into one-third? > Why are there two sexes instead of three?

The reason is that the number 2 is special - it is the smallest complex number The difference between 1 and 2 is qualitative, while the difference between 2 and 3 (and any other positive integer) is quantitative and therefore not drastic

Therefore, the binary form of many algorithms and data structures is proved to be the simplest, although some of them may be generalized, with varying degrees of increased complexity and suitable for arbitrary cardinality