shahidul_brur's blog

Is n(log n)^2 suffix array implementation good enough for contests
By shahidul_brur, 8 years ago, In English

I noticed that almost all of the programming blog shared O(n*(log n)^2) implementation for suffix array construction.

I saw O(n * log n) implementation in the book "Competitive Programming 3" — by Steven & Felix Halim. But it seems hard to understand and needs more time to code, since the code is longer compared to the O(n * log^2 n) implementation.

Besides, O(n*(log n)^2) implementation is easy to code and easy to understand.

So, my question is: Is it good enough to learn only n(log n)^2 suffix array implementation for solving problems related to suffix array in any contests? Have you seen any problem where O(n*(log n)^2) fails but O(n*(log n)) passes?

If you think that one must know O(n*(log n)) implementation, can you please share any easy to understand and comparably short code for O(n*(log n)) implementation?

Another question: any problem which is solvable by suffix tree, can be solved suffix array? If so, can we skip suffix tree and always use suffix array?

Thanks in advance.

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

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

As far as I remember there are some questions which requires you to actually walk and work in the tree, so suffix array does not always work :(

Example: https://www.hackerrank.com/contests/worldcupfinals/challenges/str-game

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

Just replace the regular sort with counting sort, this should improve the complexity to NlogN

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Would you please share a code to construct suffix array in nlogn using counting sort? This will be very helpful for me.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      You can find it on e-maxx in the middle of the wall of text. However, it's quite bad, as all the codes on that website.

      → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It's my $$$\mathcal O(n\log n)$$$ suffix array with radix_sort:74925146

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

Have you seen any problem where O(n*(log n)^2) fails but O(n*(log n)) passes?

Have you seen any problem with decent TL? ... Yes, I have. It's better to just have a prewritten .

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

If I have to manually code a suffix array I write the O(N (log N)2) version.

But if prewritten code can be used, then I use the code for the LCP-Table wrapped around the O(N) implementation from here (publication).

Some problems require an on-line construction, which afaik makes the use of suffix-trees necessary.

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

Some time ago I compared two implementations on Timus 1393 problem ... and O(Nlog2N) worked two times faster! Since then I totally abandoned O(NlogN) approach. If somebody can beat my current time with it — please let me know, maybe I'll reconsider.

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

    After reading some of your posts such as Efficient Segment tree, Fast and Furious IO... it's clear that you have a gift for implementation. It would be great if you start some implementation blogs, something like https://sites.google.com/site/indy256/algo/ . I am sure that you will have a huge number of followers :))

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could you share your implementation?

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

STL sort is very fast and I have examples of some tasks (not including SA) when replacing counting sort with STL sort (which makes complexity worse) actually improved the runtime. If TL is strict then improving that approach to n log n will probably have little significance (if any) and it is better to have O(n) prewritten.

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

Deemo used Suffix array and got accepted in IndiaHacks 2016 — Online Edition (Div. 1 + Div. 2), 16814760.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Very late but can you share where you may have learned about olog^2 n SA? I see it at geeks for geeks https://www.geeksforgeeks.org/suffix-array-set-2-a-nlognlogn-algorithm/

The problem is a lot of people in the comments claim to have bugs... I'm not sure though.

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +11 Vote: I do not like it

    Pro tip: Never trust any code on geeksforgeeks. I made that mistake twice and both times I got burned so bad. In one case they claimed it was N^2 but I read the code and it was actually N^3 (systest seemed to agree with me). Luckily, it was only in upsolving.

    There's an ancient stanford pdf with correct code, use that one instead.

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This is pretty much everything you need to know to code SA in nlog^2(n)

    → Reply