Help with Suffix Array

Revision en1, by tenshi_kanade, 2015-08-18 17:45:55

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

Tags suffix array, strings, suffix

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English tenshi_kanade 2015-08-18 17:45:55 700 Initial revision (published)