Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

SPyofgame's blog

How can I find Suffix Array in Linear effectively
By SPyofgame, history, 4 years ago, In English

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.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply