Profile photo for Ritesh Kumar Gupta

There are many good resources available in the internet.



Alert:
Before I move further, I would like to mention that there are vast differences between suffix tree and suffix array. However constructing suffix tree is bit tedious and takes long time. Also, suffix tree is bit slower than S.A because of the overhead of the constraints involved. Also, S.A is space efficient alternative to suffix tree. Every suffix tree algorithm can be systematically replaced with an algorithm that uses a suffix array enhanced with additional information (such as the LCP array) and solves the same problem in the same time complexity. So, I would explain good sources to understand Suffix Array, instead of Suffix tree.



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.

Suffix arrays – a programming contest approach is the best implementation/application tutorials for suffix array across Internet.
It gathers as many problems as possible that can be solved using the suffix arrays. Going through all the problems at the first reading would seem rather difficult for a reader who had the first contact with suffix arrays by reading this paper. In order to make the lecture easier, the problems are arranged in
an increasing difficulty order.

C++ implementations of some of the popular suffix Array problems are available at : my blog.

Reading tutorials and few implementations won't help you to understand this advanced data structure or won't help you to take a firm grip over this topic. Try to pick and solve various problems from spoj, codechef, topcoder, etc, on suffix array/tree topic.

Here are some of the problems on suffix array that I had collected from spoj, codechef and codeforces.

Problem Name Online Judge/Contest
1
Glass Beads SPOJ

2 New Distinct Substrings SPOJ

3 Stammering Aliens Live Archive2009Europe - Southwestern

4 Distinct SubstringsCategories SPOJ

5 Suffix Array SPOJ

6 I Love Strings!! UVA

7 Minimum Rotations SPOJ

8 Longest CommonSubstring SPOJ

9 GATTACA UVA

10 Glass Beads UVA

11 Lexicographical Substring Search SPOJ

12 Petr# Codeforces

13 String Codeforces

14 Martian Strings Codeforces

15 Deletion of Repeats Codeforces

16 Genetic engineering Codeforces

17 StringCategories Codeforces

18 Little Elephant and Strings Codeforces

19 Cyclical Quest Codeforces

20 Fence Codeforces

21 Life Forms UVA

22 Code Theft UVA

23 Number of Palindromes SPOJ

24 Palindromes SPOJ

25 Level Of Difference CODECHEF

26 Repeated String CODECHEF

27 Prefixes and suffixes ACM-SGU-RU

28 Lucy and the Flowers CODECHEF

Fastest Implementations: Generally, Overall complexity of building suffix array is O(n*log n) but there is an important algorithm called DC3 which computes suffix arrays in linear time O(n). Thus, suffix arrays becomes as effective as suffix tree. Source code of this coolest super fancy DC3 algorithm in C++ is available at last few pages of this PDF . The overall PDF includes beautiful explanation of the algorithm. DC3 always helped me to achieve best run-time at SPOJ.

For Solving any Suffix Array problems, We need to know:

  • Construction of Suffix array (Basic Step)


  • Finding the Longest Common Prefixes between the adjacent suffixes.(Standard LCP Array constructions)


  • Finding the LCP between any two suffixes by RMQ using Standard LCP array derived in step 2.

    I have explained first two steps in one of my answer on suffix array:
    http://qr.ae/TIoMQ
View 5 other answers to this question
About · Careers · Privacy · Terms · Contact · Languages · Your Ad Choices · Press ·
© Quora, Inc. 2025