Need O(n) suffix array tutorial

Revision en1, by sajalhsn13, 2018-09-16 11:16:54

Hello everyone,

I am trying to solve this problem. If I can build the LCP array with O(n) complexity I can easily solve it. But building LCP array requires suffix array. I know the O(n*logn*longn) algorithm. But It will give me TLE in this problem. I need the O(n) algorithm to build suffix array. I searched for it and get a paper which is too complex to understand for me. Can anyone give me a simple and well explained tutorial to build suffix array with O(n) time? It will be great help for me.

Thank you.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English sajalhsn13 2018-09-16 11:16:54 607 Initial revision (published)