Блог пользователя SPyofgame

Автор SPyofgame, история, 4 года назад, По-английски

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.

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.