Three popular algorithms for string related problems are: Suffix Array, Suffix Automaton and Suffix Tree. So what are the advantages/disadvantages of each of these? Is there any types of problems which is easy to tackle by one of these 3, but not by other 2? Let's gather these types of information in this post. :)

From theoretical perspective there is a papper Abouelhoda, Kurtz, Ohlebusch: Replacing suffix trees with enhanced suffix arrays claiming that any problem solvable by suffix tree can be solved with same time complexity using [enhanced] suffix arrays:

Here is my humble opinion:

Suffix array. It's the simplest structure, but is built in instead of linear time. Requires linear memory. It's usually easy to reforumulate complex problem in terms of suffix array, but the solution is not always easy to implement: tons of binary searches and LCPs usage is common. It's not so hard, but can be frightening in the beginning.Suffix tree. It can be built online in linear time (in contrast with suffix array), but require up toO(nΣ) memory (Σ is a size of the alphabet). Solutions that use it are very similar to ones using suffix array. They are usually a bit simpler to implement, though.Suffix automaton. It's the most unintuitive structure for me. Time and memory consumption concide with suffix tree's. However, it is easier to implement. Set of problems solved by automaton differ from the one of tree and array a lot. Automaton uses 'right contexts' instead of prefixes and it can be quite confusing, as it is for me. So, I don't use automaton, if the problem is not about "writing an automaton".I prefer suffix array on contests, but automaton may be preferrable in some cases. In contrast, my teammate likes automaton more than array. I don't remember a problem which can be solved with suffix tree only (except the training ones from Summer Informatics School).

The suffix array can be built in linear time too, and certainly faster than a suffix tree, using the Karkkainen algorithm (I've also seen it under the name DC3). Most implementations look daunting, but it is possible to prepare one which is both fast and short (easy/fast to write from a code-notebook). Of course, the

nlognone is way simpler.i prefer suffix array too~

however, some problem with strict time limit may force me to use automaton :(

There is another type of suffix array called Dynamic Extended Suffix Array which is used for online suffix array problems, here is the link http://www-igm.univ-mlv.fr/~lecroq/articles/jda2009.pdf, in practice is not so easy to implement but is very useful.

I'm currently learning all this string data-structures and I'm having troubles on how to implement them, do someone have a 'clear' implementation of them for a good understanding ? The ones I managed to find are all obscure and weird, making everything harder for beginners.

In this book, almost all the algorithms on texts are well explained, including suffix automaton.

http://www.google.com.cu/url?sa=t&rct=j&q=&esrc=s&source=web&cd=8&cad=rja&ved=0CGEQFjAH&url=http%3A%2F%2Fbooks.google.com%2Fbooks%2Fabout%2FText_Algorithms.html%3Fid%3DtSxLkRIyvoIC&ei=6d4sUsPONYfY9ATkyoCgBA&usg=AFQjCNFEkZyk_QHOcQaTzFldcBJ93rcO7g&bvm=bv.51773540,d.eWU

Many texts say that there is a relation between suffix automata of a string and suffix tree of the reverse string. I could not grab that. It would be great, if someone could explain that.

Suffix tree of the reverse string == suffix link tree of automaton of the string

Thanks