1
$\begingroup$

Let's say that we have computed a suffix tree in O(n) time, and wish to use this to create a suffix array. According to wikipedia:

A suffix tree can be built in $O(n)$ and can be converted into a suffix array by traversing the tree depth-first also in $O(n)$, so there exist algorithms that can build a suffix array in $O(n)$.

but in order to do this, the suffix tree must be traversed in lexicographical order. It is my understanding, that in order to do this, at each depth you must sort the outgoing edges and pick whichever is lexicographically the smallest, which would mean ultimately you end up sorting the entire alphabet (denoted as $k$) of whatever string you constructed the tree from, so hence $O(nk\log k)$ (assuming a well picked sorting algorithm).

I don't see how you could construct the suffix array in $O(n)$ time, even if when creating the suffix tree you sorted the edges, it would then take $O(nk\log k)$ time to make the suffix tree.

Any clarity or help on this would be much appreciated!

$\endgroup$
3
  • 1
    $\begingroup$ at each depth you must sort the outgoing edges and pick whichever is lexicographically the smallest - if the representation of the suffix tree is the same as I expect, then all outgoing edges must start with different letters. I.e. at every node you need to sort only $|\Sigma|$ edges, where $\Sigma$ is the alphabet. Therefore, the additional factor will be at most $\log |\Sigma|$, not $\log n$. Usually, the representation is even more straightforward and the sorting will use $O(n |\Sigma|)$ time. $\endgroup$ – Dmitry Apr 28 at 3:27
  • 1
    $\begingroup$ @Dmitry Yes you are correct, my mistake. Even so, that still feels like it isn't O($n$) $\endgroup$ – Recessive Apr 28 at 3:29
  • 1
    $\begingroup$ I'm not sure, but the alphabet size is probably treated as a constant, so it's $O(n \cdot f(|\Sigma|))$ for some $f$, which is $O(n)$. $\endgroup$ – Dmitry Apr 28 at 3:31

Your Answer

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

Browse other questions tagged or ask your own question.