Confused101's blog

N * (log N) Suffix array
By Confused101, history, 8 years ago, In English

I was learning suffix array. I want to know what is the need of n*(log n) suffix array construction, are there problems in which n*(log^2n) construction not sufficient. If so, Can someone please provide links to problems.

Thanks!

  • Vote: I like it
  • -5
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +10 Vote: I do not like it

http://www.spoj.com/problems/LCS/

From what i've seen, usually you would see a difference for lengths greater than 200.000, when radix-sort becomes 2-3 times faster.

→ Reply