[skrebbel]

Can anyone explain to me why this is said to be O(n) when it heavily relies on sorting?

[rullelito]

Wiki mentions https://en.wikipedia.org/wiki/Suffix_array is used for performance.

[Lichtso]

Not only that, the suffix array [1] is using counting sort O(n) instead of a comparison based O(n log n) sort. That is because they assume integer alphabets. For general alphabets they can only achieve O(n log n).

[1] https://arxiv.org/abs/1610.08305