Does the building of a suffix tree via trivial algorithm require to build a suffix trie as a first stage?

Asked Apr 22 '20 at 07:43

Active Apr 22 '20 at 07:59

Viewed 136 times

I'm just learning suffix trees/tries and trying to at first implement it via some trivial algorithm (non-linear). The trivial algorithm requires adding the suffixes of a string consequently and in some stage, we may have some suffix which will be the prefix of another suffix which requires to traverse this already existing prefix.

For example, there is a string "banana". Here we have the following suffixes:

banana$
anana$
nana$
ana$
na$
a$

Now, let's assume we have added the first 3 suffixes into the tree and currently we need to add ana. This means we need to traverse anana at first and find the longest prefix like ana and then add it. So does this algo require constructing a trie before constructing a tree?

edited Apr 22 '20 at 07:59

asked Apr 22 '20 at 07:43

https://stackoverflow.com/questions/9452701/ukkonens-suffix-tree-algorithm-in-plain-english?rq=1 – Photon Apr 22 '20 at 07:47
No, you just need a flag in each node that indicates whether the character is the last in a suffix. – 500 - Internal Server Error Apr 22 '20 at 07:48

Does the building of a suffix tree via trivial algorithm require to build a suffix trie as a first stage?

0 Answers0