13
$\begingroup$

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?

| cite | improve this question | |
$\endgroup$
9
$\begingroup$

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 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.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Could you give a pointer to the easier way to build suffix arrays in O(N lg N) time? $\endgroup$ – Randomblue Feb 19 '12 at 13:08
  • 1
    $\begingroup$ 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: webglimpse.net/pubs/suffix.pdf $\endgroup$ – zotachidil Feb 19 '12 at 22:19
7
$\begingroup$

In addition to what was mentioned (Kärkkäinen & Sanders, 2003), I think you would appreciate the "newer" version by Kärkkäinen, Sanders and Burkhard, 2006. 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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.