1
$\begingroup$

I feel stuck at this point. I have spent several days trying to get my head around the algorithm, but both resources I have [1] [2] seems to skip over whatever details that would make me comfortable trying to explain/implement it. I'm going to hope that someone here knows Farachs suffix tree algorithm, but I'll link to the paper below.

I get the individual mechanisms of the algorithm, but I don't understand how to put it all together. By starting at the first step:

(1) Creating the odd tree requires sorting every character pair of the string, but the example used, namely g = 121112212221 yields the "sorted" list l = (1,2),(1,1),(1,2),(2,1),(2,2),(2,1), and then taking the ranks of l yields. g' = 2,1,2,3,4,3. I can't see how l is sorted, or why it would help to sort it.

(2) Farach mentions that the suffix tree for g' needs to be computed recursively. Is this the only step of the algorithm that needs recursion?

[1] http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.45.4336&rep=rep1&type=pdf

[2] https://www.amazon.com/Computing-Patterns-Strings-William-Smyth/dp/0201398397

$\endgroup$
0
$\begingroup$

Not a complete answer but I hope this helps.

re :

Creating the odd tree requires sorting every character pair of the string, but the example used, namely g = 121112212221 yields the "sorted" list l = (1,2),(1,1),(1,2),(2,1),(2,2),(2,1), and then taking the ranks of l yields. g' = 2,1,2,3,4,3. I can't see how l is sorted, or why it would help to sort it.

Let,

$l$ - list

$g$ - ranks of elements of $l$ in $sorted(l)$

You can easily recover $sorted(l)$ using $l$ and $g$. You just put $i^{th}$ element of $l$ at position $g[i]$ in some new array $A$, like this,

for i = 0 to len(l): 
   A[g[i]] = l[i]

Fill out following $A$ to see it.

l = [3, 2, 4]

g = [2, 1, 3]

A = [ , , ]

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