suffix-tree 0.0.4

A Generalized Suffix Tree for any iterable, with Lowest Common Ancestor retrieval

A Generalized Suffix Tree for any Python iterable, with Lowest Common Ancestor retrieval.

pip install suffix-tree

This implementation:

• works with any Python iterable, not just strings, if the items are hashable,

• is a generalized suffix tree for sets of iterables,

• uses Ukkonen’s algorithm to build the tree in linear time,

• does constant-time Lowest Common Ancestor retrieval,

• outputs the tree as GraphViz .dot file.

This implementation follows [Gusfield1997] Chapter 6, with some differences:

• indices are 0-based (a Python convention),

• end indices point one element beyond the end (also a Python convention).

PyPi: https://pypi.org/project/suffix-tree/

[Gusfield1997]

Gusfield, Dan. Algorithms on strings, trees, and sequences. 1997. Cambridge University Press.