data-structurestriesuffix-treeprefix-tree

What is the advantage of generalized suffix tree over prefix tree?


It will be of great help if some-one explains the reason in bit detail and in which scenario one is more advantageous than the other. Thanks in advance !!


Solution

  • Prefix trees (tries) and generalized suffix trees are designed for different problems. Typically, you'd use tries to answer queries like "is string w contained in this set?" or "is w a prefix of some string in the set?" Generalized suffix trees are designed for queries like "what strings in this set contain w as a substring?" as well as many other queries, like longest common substring. For standard programming purposes, tries usually cover what's needed, but in specialized applications (particularly genomics) generalized suffix trees are more flexible.

    Hope this helps!