_Nyu_'s blog

Need help to Build Suffix Array
By _Nyu_, history, 5 years ago, In English

Is there any Linear Time algorithm to build Suffix Array? Please provide source code or algorithm link.....

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

For this you can build a suffix tree in O(n) and then convert it into a suffix array by performing a lexicographic DFS on the suffix tree.

See this for more.

→ Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Yes. At least one such algorithm is DC3. However I don't know if linear time construction is any faster than for usual input sizes.

→ Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

SA-IS algorithm has linear complexity, and is competitive with the time algorithms. You can find a simple description here and the original paper with some implementation here.

→ Reply