naive suffix tree construction in Python

Question

I'm not certain if my implementation is correct, it appears to be, but looking for any feedback as far as readability and efficiency goes. Obviously using dictionaries isn't particularly efficient space wise, but how else could you achieve O(1) lookup?

import os

def get_suffixes(string):
    return [string[i:] + "$" for i in range(len(string) + 1)]


def shared_prefix(string_a, string_b):
    return os.path.commonprefix([string_a, string_b])


def construct_suffix_tree(string):
    tree = {}
    for i in range(len(string) + 1):
        suffix = string[i:] + "$"
        insert_suffix(suffix, tree)
    return tree


def insert_suffix(string, suffix_tree):
    if len(suffix_tree) == 0:
        suffix_tree[string] = []
        return suffix_tree

    found_match = False
    for key in list(suffix_tree):
        prefix = shared_prefix(string, key)
        n = len(prefix)
        if len(prefix) > 0:
            found_match = True
            key_suffix = key[n:]
            string_suffix = string[n:]
            del suffix_tree[key]
            suffix_tree[prefix] = [key_suffix, string_suffix]

    if not found_match:
        suffix_tree[string] = []
    return suffix_tree


my_string = "banana"
print(construct_suffix_tree(my_string))

Answer 1

It's pretty readable, and all comments are pretty minor ones.

You can probably squeeze out a little performance increase, but not much. One thing you could do is to skip setting variables like n = len(prefix) (you also don't use n in the following line).

You could also consider collections.deque instead of list where relevant, which can sometimes give you a little extra speed. Or if you have the option to use list comprehension, do so.

And doing if suffix_tree: instead of if len(suffix_tree) == 0: is also faster; ca 30 ns vs 85 ns on my machine (Python 3.8.1).

On the time and space complexity, you have to make a judgement call if time or space is more important; only other way you could have O(1) lookup would be with a set.

Finally, you don't need to keep track of found_match---you can just use a for-else with a break-statement.

PS. You should be wary of mutating objects you're iterating over.