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
I think you should add s+="&"; after the line string s = "AAAA"; Try it and see if it works
Yes, it worked. Seems like I need a terminating character that is less than any character in the string. Thanks a lot!
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.That worked. Thanks.
could you post your working code as an update?
It's exactly the same, but with
s += '#'. I just needed to add a termination character to the string.