by kvh

Suffix tree for string searching

132 Stars 67 Forks Last release: Not found MIT License 16 Commits 0 Releases

Available items

No Items, yet!

The developer of this repository has not created any items for sale yet. Need a bug fixed? Help with integration? A different license? Create a request here:

Suffix Trees in Python

Based off of Mark Nelson's C++ implementation of Ukkonen's algorithm. Ukkonen's algorithm gives a O(n) + O(k) contruction time for a suffix tree, where n is the length of the string and k is the size of the alphabet of that string. Ukkonen's is an online algorithm, processing the input sequentially and producing a valid suffix tree at each character.

How to use

string = "I need to be searched!"
tree = SuffixTree(string)
index_of_need = tree.find_substring("need")

Usage note

This library is mostly an academic exercise. If you need an efficient library I would recommend a python-wrapped c implementation, such as this one.

We use cookies. If you continue to browse the site, you agree to the use of cookies. For more information on our use of cookies please see our Privacy Policy.