Suffix Tree in Python I was wondering why the following implementation of a Suffix Tree is 2000 times slower than using a similar data structure in C++ (I tested it using python3, pypy3 and pypy2). I know the bottleneck is the traverse method, do you spot chance of optimisation in the following code? Thanks!

from sys import stdin, stdout, stderr, setrecursionlimit
setrecursionlimit(100000)

def read():
    return stdin.readline().rstrip()

def readint():
    return int(read())

def make_node(_pos, _len):
    global s, n, sz, to, link, fpos, slen, pos, node
    fpos[sz] = _pos
    slen[sz] = _len
    sz += 1
    return sz-1

def go_edge():
    global s, n, sz, to, link, fpos, slen, pos, node
    while (pos &gt; slen[to[node].get(s[n - pos], 0)]):
        node = to[node].get(s[n - pos], 0)
        pos -= slen[node]

def add_letter(c):
    global s, n, sz, to, link, fpos, slen, pos, node
    s[n] = c
    n += 1
    pos += 1
    last = 0
    while(pos &gt; 0):
        go_edge()
        edge = s[n - pos]
        v = to[node].get(edge, 0)
        t = s[fpos[v] + pos - 1]
        if (v == 0):
            to[node][edge] = make_node(n - pos, inf)
            link[last] = node
            last = 0
        elif (t == c):
            link[last] = node
            return
        else:
            u = make_node(fpos[v], pos - 1)
            to[u][c] = make_node(n - 1, inf)
            to[u][t] = v
            fpos[v] += pos - 1
            slen[v] -= pos - 1
            to[node][edge] = u
            link[last] = u
            last = u
        if(node == 0):
            pos -= 1
        else:
            node = link[node]

def init_tree(st):
    global slen, ans, inf, maxn, s, to, fpos, slen, link, node, pos, sz, n

    inf = int(1e9)
    maxn = len(st)*2+1 #int(1e6+1)
    s = [0]*maxn
    to = [{} for i in range(maxn)]
    fpos, slen, link = [0]*maxn, [0]*maxn, [0]*maxn

    node, pos = 0, 0
    sz = 1
    n = 0

    slen[0] = inf
    ans = 0
    for c in st:
        add_letter(ord(c))


text = "TTTTTTTTTT" + 1777*"A" + "$"
query = 1750*"A"

def traverse_edge(st, idx, start, end):
    global len_text, len_st
    k = start
    while k &lt;= end and k &lt; len_text and idx &lt; len_st:
        if text[k] != st[idx]:
            return -1
        k += 1
        idx += 1
    if idx == len_st:
        return idx
    return 0

def edgelen(v, init, e):
    if(v == 0):
        return 0
    return e-init+1

def dfs(node, leafs, off):
    if not node:
        return
    k, tree = node
    if not isinstance(tree, int): # it is a node pointing to other nodes
        for kk, value in tree.items():
            if slen[value] &gt; 190000000:
                leafs.append(fpos[value]-off)
            else:
                dfs((kk, to[value]), leafs, off+slen[value])

def traverse(v, st, idx, depth=0):
    global len_st
    result = cache.get((v, st), -2)
    if result != -2:
        return result
    r = -1
    init = fpos[v]
    end = fpos[v]+slen[v]
    e = end-1
    if v != 0:
        r = traverse_edge(st, idx, init, e)
        if r != 0:
            if r == -1:
                cache[(v, st)] = []
                return []
            depth += r
            # Here is when we found a match
            leafs = []
            dfs((v, to[v]), leafs, depth)
            #return reversed(leafs)
            return leafs
    idx = idx + edgelen(v, init, e)
    if idx &gt; len_st:
        cache[(v, st)] = []
        return []
    k = ord(st[idx])
    children = to[v]
    if k in children:
        vv = children.get(k, 0)
        matches = traverse(vv, st, idx, depth)
        cache[(v, st)] = matches
        return matches
    return []


def main():
    global text, len_st, len_text, cache
    init_tree(text)
    len_text = len(text)
    len_st = len(query)
    r = []
    #cache = {}
    for runs in range(1000):
        cache = {}
        matches = traverse(0, query, 0)
        r.append("\n".join(str(m) for m in matches))
    stdout.write("\n".join(r)+"\n")

main()
So, about all those globals. They make your code really hard to read, I have almost no idea what is going on (after having read it twice). The general recommendation is to only use global objects if you really have to. Otherwise pass the objects either as arguments to the function, or write a class which has the relevant variables as attributes and keep the state like this.

Another thing that makes your code a lot easier to understand (both for other people and for yourself in two months time), are docstrings, which document what each function does, the parameters it takes and what it returns or modifies.