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:
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 nlogn one 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