Hello guys,
is there a tutorial for implementation and applications of suffix tree data-structure ??
or some paper or any link that helps you understand ?? I couldn’t find much of it !,
And also are suffix array and suffix trees two different things ??
it’d be helpful if anybody can provide details regarding that and also some problems for solving - related to suffix trees/arrays !!
Thank you 
!
@mecodesta >> You can try these tutorials idea based, C implementation; and these problems:
– Are Suffix Array and Suffix Trees two different thing?
Yes, they are two different things.Suffix Array is an efficient alternatives to Suffix Tree.
Read **More.
– Is there any tutorial for suffix Arry data-structure ?
There are many:
I personally like Suffix arrays: A new method for on-line string searches , by Udi Manber and Gene Myers.
The neat implementation of above paper in C++ can be found at TopCoder Forum.
– Is there a tutorial for implementation and applications of suffix tree data-structure ?
Suffix arrays – a programming contest approach is the best implementation/application tutorials for suffix array across Internet.
C++ implementations of some of the popular suffix Array problems are available at : my blog.
Fastest or linear time implementation of Suffix array construction using DC3 algorithm: Source code in C++ is available at last few pages of this PDF . It helped me to achieve best run-time at SPOJ.
– Can you lists few suffix trees/arrays related problems for solving?
| Problem Name | Online Judge | Year | Contest | ||
|---|---|---|---|---|---|
| 1 | Glass Beads | Categories | SPOJ | ||
| 2 | New Distinct Substrings | Categories | SPOJ | ||
| 3 | Stammering Aliens | Categories | Live Archive | 2009 | Europe - Southwestern |
| 4 | Distinct Substrings | Categories | SPOJ | ||
| 5 | Suffix Array | Categories | SPOJ | ||
| 6 | I Love Strings!! | Categories | UVA | ||
| 7 | Minimum Rotations | Categories | SPOJ | ||
| 8 | Longest Common Substring | Categories | SPOJ | ||
| 9 | GATTACA | Categories | UVA | ||
| 10 | Glass Beads | Categories | UVA | ||
| 11 | Lexicographical Substring Search | Categories | SPOJ | ||
| 12 | Petr# | Categories | Codeforces | Codeforces Beta Round #86 (Div. 1 Only) & Codeforces Beta Round #86 (Div. 2 Only) | |
| 13 | String | Categories | Codeforces | Codeforces Beta Round #94 (Div. 1 Only) & Codeforces Beta Round #94 (Div. 2 Only) | |
| 14 | Martian Strings | Categories | Codeforces | Codeforces Round #106 (Div. 2) | |
| 15 | Deletion of Repeats | Categories | Codeforces | Codeforces Beta Round #19 | |
| 16 | Genetic engineering | Categories | Codeforces | Yandex.Algorithm 2011 Round 2 | |
| 17 | String | Categories | Codeforces | Codeforces Beta Round #92 (Div. 1 Only) | |
| 18 | Little Elephant and Strings | Categories | Codeforces | Codeforces Round #129 (Div. 1) | |
| 19 | Cyclical Quest | Categories | Codeforces | Codeforces Round #146 (Div. 1) & Codeforces Round #146 (Div. 2) | |
| 20 | Fence | Categories | Codeforces | Codeforces Round #144 (Div. 1) | |
| 21 | Life Forms | Categories | UVA | ||
| 22 | Code Theft | Categories | UVA | ||
| 23 | Number of Palindromes | Categories | SPOJ | ||
| 24 | Palindromes | Categories | SPOJ | ||
| 25 | Level Of Difference | Categories | CODECHEF | ||
| 26 | Repeated String | Categories | CODECHEF |
Love you man <3 !! thanks a million, really really helpful !!!
@ritesh_gupta i went through the paper, your blog, and that PDF about “suffix arrays in contest programming” - the PDF kind of follows a different implementation for suffix arrays … from the one mentioned in your blog/topcoder tutorial ! i just have a doubt about which one is efficient !! the one mentioned in the PDF seems simple but i’m not sure if it’ll squeeze through tough time constraints under a java implementation !
PDF one is easy implementation. Mine and TC is bit tough . The fastest implementation is DC3 Algortithm For Suffix Array.The code is given in last pages of this pdf http://algo2.iti.kit.edu/documents/jacm05-revised.pdf
Don’t worry about implementation. Just knw how to code - 1. Suffix Array construction. 2. Standard LCP array 3.LCP between any suffixes. With these three things u can solve any suffix array question
@ritesh_gupta great job man…is there some tutorials,set of questions to practice for dyanamic programming…thanx in advance
