Yes. By pigeonhole principle.

Oops! Actually... Wow, I didn't know that my inattentiveness can be that hight of a level. Because I read the very same article on cppreference and tried to find complexity analysis. But because I failed, I started to mess with source files. I guess, sometimes happens :-)

https://web.stanford.edu/class/cs97si/suffix-array.pdf

There you can find an explanation of O(nlog²n) algorithm with examples + code. (I don't know for sure, but I think they don't mention that while sorting suffixes you actually sort rotations(cyclic shifts) of a string, but because of '$' at the end it will be still correct).

To make it O(nlogn) however you should use as Gtaumaturgo mentioned O(n) sort for equivalence classes. One can use radix sort for that. For example, to sort a list of numbers you will sort them firstly by the least significant digit, then by the second least significant digit and so on but using stable counting sort. Using this analogy you can sort pairs of numbers : sort the pair's second member and then the first.

Now, we have 2^k suffix prefixes sorted, we want to get 2^(k + 1) suffix prefixes sorted. Let's note that second part is already being sorted, so that for every i : new_p[i] = (p[i] — 2^k) % n (we just make prefixes point to a start of 2^(k + 1) substring, that's all). Then using these new prefixes and information about equivalence classes we can sort them using stable counting sort in O(n) giving in total O(nlogn) algorithm.

Well, I'm getting worse every round. I knew how to solve A task, but after runtime error I started to solve problem E... Solved A 18 minutes before the end. :( Why am I so bad?