<p>In addition to what was mentioned (<a href="http://dl.acm.org/citation.cfm?id=1759301">Kärkkäinen &amp; Sanders, 2003</a>), I think you would appreciate the "newer" version by <a href="http://dl.acm.org/citation.cfm?id=1217858">Kärkkäinen, Sanders and Burkhard, 2006</a>. The algorithm basically follows the structure of Farach's algorithm. It is arguably conceptually simpler, but the real bonus is that they provide the reader with a implementation of the algorithm. It is only about 50 lines of C++, so there are indeed no hidden details.</p>

CC BY-SA 3.0
2012-02-17T21:58:31.920Z
2012-02-17T22:28:39.780Z
2012-02-17T22:28:39.780Z
Juho
<p>I'm not sure if there were any new results directly simplifying the construction of suffix trees. However, there has been at least <a href="http://dl.acm.org/citation.cfm?id=1759301" rel="nofollow">one result</a> giving a very simple algorithm for constructing suffix arrays in linear time.</p>

<p>Note that there's more than a conceptual equivalence between these two data structures, since you can use a suffix array (with $\cal{O}(1)$ time for querying the longest common prefix) to build an equivalent suffix tree. This should be a relatively simple exercise, but I can give more details if required.</p>

<p>Also, for practical purposes it's even easier to build suffix arrays in $\cal{O}(n \lg n)$ time, but I guess I'm going slightly off-topic here.</p>

CC BY-SA 3.0
2012-02-19T13:08:17.100Z
Could you give a pointer to the easier way to build suffix arrays in O(N lg N) time?
Randomblue
CC BY-SA 3.0
2012-02-19T22:19:34.243Z
Label all the suffixes of length 2^k with an integer such that the labels correspond to the order relation between suffixes. The first  step (k = 0) is obvious. To compute the labels at step k, use the labels from step k-1, and do a radix sort. This paper should be easy to understand: http://webglimpse.net/pubs/suffix.pdf
zotachidil
CC BY-SA 3.0
2012-02-17T16:52:44.820Z
2012-02-19T14:38:43.887Z
2012-02-19T14:38:43.887Z
zotachidil
<p>In 1973 Weiner gave the first linear-time construction of suffix trees. The algorithm was simplified in 1976 by McCreight, and in 1995 by Ukkonen. Nevertheless, I find Ukkonen's algorithm relatively involved conceptually.</p>

<p>Has there been simplifications to Ukkonen's algorithm since 1995?</p>

CC BY-SA 3.0
2012-02-17T16:44:41.793Z
Farach et el 1998. I think this is a good place to start reading: http://scholar.google.co.uk/scholar?q=Linear+Work+Suffix+Array+Construction
Radu GRIGore
<ds.algorithms>
Conceptually simple linear-time suffix tree constructions
Randomblue
# Conceptually simple linear-time suffix tree constructions

(Asked by: username_0 on 2012-02-17)

In 1973 Weiner gave the first linear-time construction of suffix trees. The algorithm was simplified in 1976 by McCreight, and in 1995 by Ukkonen. Nevertheless, I find Ukkonen's algorithm relatively involved conceptually.

Has there been simplifications to Ukkonen's algorithm since 1995?

**Tags:** ds.algorithms

> **Comments:**
> **username_1**: Farach et el 1998. I think this is a good place to start reading: http://scholar.google.co.uk/scholar?q=Linear+Work+Suffix+Array+Construction  

---

## 2 answers

### Answer by username_3 on 2012-02-17. Score: 9 | Accepted answer

I'm not sure if there were any new results directly simplifying the construction of suffix trees. However, there has been at least [one result](http://dl.acm.org/citation.cfm?id=1759301) giving a very simple algorithm for constructing suffix arrays in linear time.

Note that there's more than a conceptual equivalence between these two data structures, since you can use a suffix array (with $\cal{O}(1)$ time for querying the longest common prefix) to build an equivalent suffix tree. This should be a relatively simple exercise, but I can give more details if required.

Also, for practical purposes it's even easier to build suffix arrays in $\cal{O}(n \lg n)$ time, but I guess I'm going slightly off-topic here.

> **Comments:**
> **username_0**: Could you give a pointer to the easier way to build suffix arrays in O(N lg N) time?  
> **username_3**: Label all the suffixes of length 2^k with an integer such that the labels correspond to the order relation between suffixes. The first  step (k = 0) is obvious. To compute the labels at step k, use the labels from step k-1, and do a radix sort. This paper should be easy to understand: http://webglimpse.net/pubs/suffix.pdf  

---

### Answer by username_2 on 2012-02-17. Score: 7

In addition to what was mentioned ([Kärkkäinen & Sanders, 2003](http://dl.acm.org/citation.cfm?id=1759301)), I think you would appreciate the "newer" version by [Kärkkäinen, Sanders and Burkhard, 2006](http://dl.acm.org/citation.cfm?id=1217858). The algorithm basically follows the structure of Farach's algorithm. It is arguably conceptually simpler, but the real bonus is that they provide the reader with a implementation of the algorithm. It is only about 50 lines of C++, so there are indeed no hidden details.


---

