Thanks to Suffix Array Tutorial from Codeforces I could learn easily how to build Suffix Array and solve some problems
I learn about $$$O(n \log^2(n))$$$ solution and optimize it into $$$O(n \log(n)$$$, it is fast and good. In some contests, I saw some div-1 rankers discuss about $$$O(n)$$$ solution. Now I am wondering if there is an simple implementation but efficient Suffix Array in Linear Time and Space ?
From their conversation about Linear Solution, I read from this paper and this too but I am not be able to implement it. I know those implementations are hard and higher above my levels but I just curiously to know about the implementation
Thanks for reading, sorry if this blog waste your time.
It is not too hard to implement this algorithm. The paper even provides a C++ implementation at the end. And in practice it is indeed faster than the $$$\mathcal{O}(n \log(n))$$$ algorithm.