mutux/ukkonen-s-suffix-tree-algorithm

Ukkonen's suffix tree algorithm, a complete version implemented in Python

ukkonen-s-suffix-tree-algorithm's Issues

O(n^2) time complexity due to list copy

There is a copy of list in unfold function. It leads to O(len(remains)) time complexity for this operation. And due to being inside while remainder > 0 this gains O(n^2) time complexity for the whole implementation (e.g. for "aaaaab").

Does not re-set parent key of existing leaf correctly on split

When a leaf node is split, the parentkey of existing node is not updated to point to internal node.
This needs to be added: bnode.setparentkey((newnode, chars[start + actlen]))

Here's a patch to add it:
suffixtree_setparentkey_on_split.patch

Uses Python 2 syntax

I tried to translate to Python 3 but the meaning of the double parentheses in the setoutedge definition eludes me.

def setoutedge(self, key, (anode, label_start_index, label_end_index, bnode)):

I guessed it would mean

def setoutedge(self, key, anode=None, label_start_index=None, label_end_index=None, bnode=None):

but implementing this change just broke the code in new ways. Could you please explain what this definition means?