Suffix Trees

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 :slight_smile: !

10 Likes

@mecodesta >> You can try these tutorials idea based, C implementation; and these problems:

this, that.

13 Likes

@bugkiller , it was helpful ! thanks !!

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
57 Likes

@mecodesta: Please show some love by voting up an answer if it was helpful to you. :slight_smile:

9 Likes

@admin : sure thing :smiley:

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 :slight_smile:

//