Блог пользователя shahidul_brur

Автор shahidul_brur, 7 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +15
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +29 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

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 .

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

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.

»
7 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

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.

»
7 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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.

»
7 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    5 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

    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.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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