How can I find Suffix Array in Linear effectively

Revision en1, by SPyofgame, 2020-07-04 15:55:46

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.

Tags #suffix_array

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English SPyofgame 2020-07-04 15:55:46 911 Initial revision (published)