tenshi_kanade's blog

Help with Suffix Array
By tenshi_kanade, history, 9 years ago, In English

Hi. I need a little help with an algorithm...

I've recently read the chapter on Suffix Array from the book Competitive Programming 2, and I've implemented it using the O(NlogN) method described there. It works, but only as long as there isn't a suffix which is itself a suffix of another suffix. For example, it doesn't work for the simple string "AAAA". I tried copying/pasting the code written in the book to make sure it wasn't my code that was wrong, but it didn't work either.

So, my question is: How do we overcome that problem and make the algorithm work even for those strings?

Here's the implementation in C++: Suffix Array

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

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

I think you should add s+="&"; after the line string s = "AAAA"; Try it and see if it works

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

    Yes, it worked. Seems like I need a terminating character that is less than any character in the string. Thanks a lot!

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

Yes, this algorithm is for sorting cyclic shifts rather than suffixes of a string so all you need is to add a special character to its end (like #) which is less than any character from the string's alphabet.

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

could you post your working code as an update?

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

    It's exactly the same, but with s += '#'. I just needed to add a termination character to the string.

    → Reply