I noticed that almost all of the programming blog shared O(n*(log n)^2) implementation for suffix array construction.
I saw O(n * log n) implementation in the book "Competitive Programming 3" — by Steven & Felix Halim. But it seems hard to understand and needs more time to code, since the code is longer compared to the O(n * log^2 n) implementation.
Besides, O(n*(log n)^2) implementation is easy to code and easy to understand.
So, my question is: Is it good enough to learn only n(log n)^2 suffix array implementation for solving problems related to suffix array in any contests? Have you seen any problem where O(n*(log n)^2) fails but O(n*(log n)) passes?
If you think that one must know O(n*(log n)) implementation, can you please share any easy to understand and comparably short code for O(n*(log n)) implementation?
Another question: any problem which is solvable by suffix tree, can be solved suffix array? If so, can we skip suffix tree and always use suffix array?
Thanks in advance.